【最大流Dinic模板】HDU1532&POJ1273-Drainage Ditches（16/3/6更正）

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 using namespace std;

 const int MAXN=;

 const int INF=0x7fffffff;

 int n,m;//n:edges,m:points

 struct node

 {

        int to,pos,cap;

 };

 vector<node> E[MAXN];

 int vis[MAXN];

 void addedge(int u,int v,int w)

 {

      node x;

      x.to=v; x.pos=E[v].size(); x.cap=w;

      E[u].push_back(x);

      x.to=u; x.pos=E[u].size()-; x.cap=;

      E[v].push_back(x);

 }

 int dfs(int s,int t,int f)

 {

     int ret=;

     if (s==t) return f;

     vis[s]=;//不要忘记这里要设置为访问过

     for (int i=;i<E[s].size();i++)

     {

         node &tmp=E[s][i];

         if (vis[tmp.to]== && tmp.cap>)

         {

             int delta=dfs(tmp.to,t,min(tmp.cap,f));

             if (delta>)

             {

                 ret+=delta;

                tmp.cap-=delta;

                E[tmp.to][tmp.pos].cap+=delta;

                f-=delta;

             }

         }

     }

     return ret;

 }

 int maxflow(int u,int v)

 {

     int flow=;

     for (;;)

     {

         memset(vis,,sizeof(vis));

         int f=dfs(u,v,INF);

         if (f==) return flow;

            else flow+=f;

     }

 }

 int main()

 {

     while(~scanf("%d%d",&n,&m))

     {

           memset(E,,sizeof(E));

           for (int i=;i<n;i++)

           {

               int x,y,z;

               scanf("%d%d%d",&x,&y,&z);

               addedge(x,y,z);

           }

           cout<<maxflow(,m)<<endl;

     }

     return ;

 }

2016/3/6更正：建立一个ret，每次递归不是找到一条增广路径就返回的..之前写的和FordFulkerson效率超不多orz