1 #include<iostream> 2 #include<vector> 3 #include<queue> 4 #include<cstring> 5 using namespace std; 6 const int maxn=1024; 7 const int inf=1<<30; 8 struct Edge{ 9     int from,to,flow,cap;10 };11 struct Dinic{12     int vis[maxn],cur[maxn],d[maxn];13     vector<Edge> edges;14     vector<int> G[maxn];15     int s,t;16     void addEdge(int from,int to,int cap)17     {18         edges.push_back((Edge){from,to,0,cap});19         G[from].push_back(edges.size()-1);20         edges.push_back((Edge){to,from,0,0});21         G[to].push_back(edges.size()-1);22     }23     int BFS()24     {25         memset(vis,0,sizeof(vis));26         queue<int> Q;27         Q.push(s);28         vis[s]=1;29         d[s]=0;30         while(!Q.empty()){31             int x=Q.front();Q.pop();32             for(int i=0;i<G[x].size();i++){33                 Edge& e=edges[G[x][i]];34                 if(!vis[e.to]&&e.cap>e.flow){35                     vis[e.to]=1;36                     d[e.to]=d[x]+1;37                     Q.push(e.to);38                 }39             }40         }41         return vis[t];42     }43     int DFS(int u,int a)44     {45         if(u==t||a==0) return a;46         int flow=0,f;47         for(int& i=cur[u];i<G[u].size();i++){48             Edge& e=edges[G[u][i]];49             if(d[e.to]==d[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0){50                 e.flow+=f;51                 edges[G[u][i]^1].flow-=f;52                 flow+=f;53                 a-=f;54                 if(!a) break;55             }56         }57         return flow;58     }59     int MaxFlow(int ss,int tt)60     {61         int ans=0;62         s=ss,t=tt;63         while(BFS()){64             memset(cur,0,sizeof(cur));65             ans+=DFS(s,inf);66         }67         return ans;68     }69 };70 Dinic solver;71 int main()72 {73     int n,m;74     cin>>n>>m;75     for(int i=1;i<=m;i++){76         int from,to,cap;77         cin>>from>>to>>cap;78         solver.addEdge(from,to,cap);79     }80     cout<<solver.MaxFlow(1,n);81     return 0;82 }