poj 1273 Drainage Ditches(网络流)

题意：给出n个点，m条边，给出边的起点和终点以及流量，其中1为源点，n为汇点，求最大流

模板题

#include<bits/stdc++.h>
using namespace std;
const int maxn=205;
const int INF=0x7fffffff;
struct edge{int from,to,cap,flow;};

struct DINIC{
    int n,m,s,t;
    vector<edge> edges;
    vector<int> g[maxn];
    int d[maxn],cur[maxn];
    bool vis[maxn];

    void add(int from,int to,int cap){
        edges.push_back((edge){from,to,cap,0});
        edges.push_back((edge){to,from,0,0});
        m=edges.size();
        g[from].push_back(m-2);
        g[to].push_back(m-1);
    }

    bool bfs(){
        memset(vis,0,sizeof(vis));
        queue<int> q;
        q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!q.empty()){
            int x=q.front();q.pop();
            for(int i=0;i<g[x].size();i++){
                edge& e=edges[g[x][i]];
                if(!vis[e.to]&&e.cap>e.flow){
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int dfs(int x,int a){
        if(x==t||a==0)return a;
        int flow=0,f;
        for(int& i=cur[x];i<g[x].size();i++){
            edge& e=edges[g[x][i]];
            if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0){
                e.flow+=f;
                edges[g[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0)break;
            }
        }
        return flow;
    }

    int maxflow(int s,int t){
        this->s=s;this->t=t;
        int flow=0;
        while(bfs()){
            memset(cur,0,sizeof(cur));
            flow+=dfs(s,INF);
        }
        return flow;
    }

    void init(int n){
        this->n=n;m=0;
        edges.clear();
        for(int i=0;i<maxn;i++)g[i].clear();
        memset(d,0,sizeof(d));
    }

}dinic;

int main(){
    int n,m,u,v,w;
    while(cin>>m>>n){
        dinic.init(n);
        for(int i=0;i<m;i++){
            cin>>u>>v>>w;
            dinic.add(u,v,w);
        }
        cout<<dinic.maxflow(1,n)<<endl;
    }
    return 0;
}