求網絡流的最大流。
注意：可能出現重邊！比如第一次c[u][v]=w1，又有c[u][v]=w2，那么從u到v的容量應該為w1+w2！
以下是我的代碼：
#include<queue>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define kS 1
#define kT n
using namespace std;
const int kMaxn(207);
int n,m,maxflow,c[kMaxn][kMaxn],f[kMaxn][kMaxn];
int main()
{
while(scanf("%d%d",&m,&n)==2)
{
memset(c,0,kMaxn*kMaxn*sizeof(int));
memset(f,0,kMaxn*kMaxn*sizeof(int));
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
c[u][v]+=w;
}
maxflow=0;
while(true)
{
int d[kMaxn],p[kMaxn];
queue<int> q;
memset(d,0,kMaxn*sizeof(int));
d[kS]=0x7f7f7f7f;
q.push(kS);
while(!q.empty())
{
int u(q.front());q.pop();
for(int v=1;v<=n;v++)
if(!d[v] && c[u][v]>f[u][v])
{
p[v]=u;q.push(v);
d[v]=min(d[u],c[u][v]-f[u][v]);
}
}
if(d[kT]==0)
break;
maxflow+=d[kT];
for(int u=kT;u!=kS;u=p[u])
{
f[p[u]][u]+=d[kT];
f[u][p[u]]-=d[kT];
}
}
printf("%d\n",maxflow);
}
return 0;
}
posted on 2011-05-28 16:55
lee1r 閱讀(195)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論