HDU OJ 3549 Flow Problem 【最大流入门】

原题连接：http://acm.hdu.edu.cn/showproblem.php?pid=3549

题意：不用费话了，题上已经很清楚了。

思路：就是一个入门的最大流问题，关键是找增广路。这是第一次做最大流纪念一下，呵呵。。

AC代码：

#include<queue>using namespace std;int cap[20][20],flow[20][20];// 容量。流量int Max_flow(int t){int s=1,i,j,f=0,p[20],a[20];// p代表上一个节点，a代表残量。memset(flow,0,sizeof(flow));queue<int> Q ;while(1){while(!Q.empty())Q.pop();memset(a,0,sizeof(a));Q.push(s);a[s]=99999999;while(!Q.empty()){i =Q.front();if(i==t)break;Q.pop();for(j=1;j<=t;j++){if(i!=j&&!a[j]&&cap[i][j]>flow[i][j]){p[j]=i;Q.push(j);a[j]= a[i]>cap[i][j]-flow[i][j]? cap[i][j]-flow[i][j]:a[i];}}}if(!a[t]) return f;//找不到增广路，说明此时已经是最大流了。for(i=t;i!=s;i=p[i]){flow[i][p[i]] -=a[t];flow[p[i]][i] +=a[t];}f+=a[t];//printf("f------->>---%d\n",f);}}int main(){int a,b,c,n,m,ncase,i;scanf("%d",&ncase);for(i=1;i<=ncase;i++){scanf("%d %d",&n,&m);memset(cap,0,sizeof(cap));while(m--){scanf("%d%d%d",&a,&b,&c);if(a==b)continue;cap[a][b]+=c;}m=Max_flow(n);printf("Case %d: %d\n",i,m);}}