题目大意：求两点之间的最大流；
题目解析：思想就是迭代dfs找增广路径，直到找不到位置，注意要更新残余网络；
AC代码：
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<vector> using namespace std; const int inf=0x3fffffff; const int maxn=1010; struct node { int to,cap,rev; node(int a,int b,int c) { to=a; cap=b; rev=c; } }; vector<node>vec[maxn]; bool used[maxn]; void add_edge(int from,int to,int cost) { vec[from].push_back(node(to,cost,vec[to].size())); vec[to].push_back(node(from,0,vec[from].size()-1)); } int dfs(int u,int v,int cost) { if(u==v) return cost; used[u]=true; int i; for(i=0;i<vec[u].size();i++) { node &temp=vec[u][i]; if(!used[temp.to]&&temp.cap>0) { int d=dfs(temp.to,v,min(cost,temp.cap)); if(d>0) { temp.cap-=d; vec[temp.to][temp.rev].cap+=d; return d; } } } return 0; } int max_flow(int u,int v) { int flow=0; while(1) { memset(used,0,sizeof(used)); int res=dfs(u,v,inf); if(res==0) return flow; flow+=res; } } int main() { int n,m,i; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<maxn;i++) { vec[i].clear(); } for(i=0;i<n;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add_edge(a,b,c); } printf("%d\n",max_flow(1,m)); } return 0; }
