网络流入门@_@,此处本人用的刘汝佳的Dinic模板
#include<bits/stdc++.h> using namespace std; const int INF = 0x3f3f3f3f; struct Edge { int from,to,cap,flow; }; int n,s,t,m; struct Dinic { , M = ; //N对应点数 vector<Edge> edges; vector<int> G[N]; bool vis[N]; int d[N]; int cur[N]; void init() { ; i<=n; i++) G[i].clear(); edges.clear(); } void AddEdge(int from,int to,int cap) { edges.push_back((Edge) { }); edges.push_back((Edge) { to,, }); int w=edges.size(); G[); G[to].push_back(w-); } bool bfs() { memset(vis,,sizeof(vis)); queue<int>Q; d[s] = ; Q.push(s); vis[s]=; while (!Q.empty()) { int x = Q.front(); Q.pop(); ; i<G[x].size(); i++) { Edge e=edges[G[x][i]]; if (!vis[e.to]&&e.cap>e.flow) { vis[e.to]=; d[e.to] = d[x] + ; Q.push(e.to); } } } return vis[t]; } int dfs(int x, int a) { ) return a; ,f; for (int&i = cur[x] ; i<G[x].size(); i++) { Edge& e=edges[G[x][i]]; &&(f=dfs(e.to,min(a,e.cap-e.flow)))>) { e.flow+=f; edges[G[x][i]^].flow-=f; //流量增大意味着净容量减少 flow+=f; //反向边容量表示了正向边的流量 a -= f; )break; } } return flow; } int Maxflow(int s, int t) { ; while (bfs()) { memset(cur,,sizeof(cur)); flow += dfs(s, INF); } // for(int i=1;i<=n;i++) // for(int j=0;j<G[i].size();j++) // printf("from:%d to:%d cap:%d flow:%d\n",i,edges[G[i][j]].to,edges[G[i][j]].cap,edges[G[i][j]].flow); return flow; } } g; int main() { while(~scanf("%d%d",&m,&n)) { g.init(); s=; t=n; ; i<m; i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); g.AddEdge(a,b,c); } printf("%d\n",g.Maxflow(s,t)); } }