试题 算法训练 网络流裸题

资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
　　一个有向图，求1到N的最大流
输入格式
　　第一行N M，表示点数与边数
　　接下来M行每行s t c表示一条从s到t的容量为c的边
输出格式
　　一个数最大流量
样例输入
6 10
1 2 4
1 3 8
2 3 4
2 4 4
2 5 1
3 4 2
3 5 2
4 6 7
5 4 6
5 6 3
样例输出
8

数据约定：
n<=1000 m<=10000

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
#define ll long long

const int INF = 0x3f3f3f3f;
const int maxn = 200000;
#define MAXN 200000


int n, m, s, t; // s是源点，t是汇点
bool vis[MAXN];
struct Edge
{
    int to,next;
    ll w;
}edges[maxn];
ll last[maxn],flow[maxn];


int head[maxn],cnt = 1;
inline void add(int from,int to,ll w)
{
    edges[++cnt].w = w;
    edges[cnt].to = to;
    edges[cnt].next = head[from];
    head[from] = cnt;
}
inline ll bfs()
{
    memset(last,-1,sizeof(last));
    queue<int> q;
    q.push(s);
    flow[s] = INF;
    while(!q.empty())
    {
        int p = q.front();
        q.pop();
        if(p==t) break;
        for(int eg=head[p]; eg; eg=edges[eg].next)
        {
            int to = edges[eg].to;
            ll vol = edges[eg].w;
            if(vol>0 && last[to]==-1)
            {
                last[to] = eg;
                flow[to] = min(flow[p],vol);
                q.push(to);
            }
        }
    }
    return last[t] != -1;
}
inline ll EK()
{
    ll maxflow = 0;
    while(bfs())
    {
        maxflow += flow[t];
        for(int i=t; i!=s; i=edges[last[i]^1].to)
        {
            edges[last[i]].w -= flow[t];
            edges[last[i]^1].w += flow[t];
        }
    }
    return maxflow;
}
int main(){

    cin>>n>>m;
    s= 1; t = n;

    for(int i=1; i<=m; ++i){
        int u,v;
        ll w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    cout<<EK()<<endl;
    return 0;
}