记录一下模板
;Edge {int from,to,cap,flow;};struct Dinic {int n,m,s,t;vector<Edge>edges;vector<int>G[maxn];bool vis[maxn];int d[maxn];int cur[maxn];void addEdge(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);}void init(){edges.clear();for(int i=1;i<=maxn;i++) G[i].clear();}bool Bfs() {memset(vis,0,sizeof(vis));queue<int>Q;while(!Q.empty()) Q.pop();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;}};int main(){int T;int n,k;Dinic slove;while(scanf(“%d”,&T)==1){int cas=0;while(T–){scanf(“%d%d”,&n,&k);slove.init();while(k–){int x,y,z;scanf(“%d%d%d”,&x,&y,&z);slove.addEdge(x,y,z);}printf(“Case %d: %d\n”,++cas,slove.maxflow(1,n));}}}
，希望有一天，自己也像他们一样，踩着单车上路，
