http://poj.org/problem?id=1273赤裸裸的網(wǎng)絡(luò)最大流問題：剛剛學(xué)的EK：
#include<stdio.h>
#include<string.h>
#include<math.h>
int map[205][205],pre[205],vis[205],que[200005];
int m,n,ans;
int min(int s,int t)
{
if (s<=t)
return s;
return t;
}
int bfs(int s,int t)
{
int head,tail,i,u;
memset(vis,1,sizeof(vis));
head=1;tail=1;
vis[s]=0;
que[1]=s;
while (head<=tail)
{
u=que[head++];
for (i=1;i<=n ;i++ )
if (vis[i]&&map[u][i])
{
pre[i]=u;
if (i==t)
return 1;
que[++tail]=i;
vis[i]=0;
}
}
return 0;
}
int dfs(int s,int t)
{
int i;
for (i=1;i<=n ;i++ )
if (vis[i]&&map[s][i])
{
pre[i]=s;
if (i==t)
return 1;
vis[i]=0;
if (!dfs(i,t))
vis[i]=1;
else
return 1;
}
return 0;
}
int end(int s,int t)
{
int i,sum=1000000000;
for (i=t;i!=s ;i=pre[i] )
sum=min(sum,map[pre[i]][i]);
for (i=t;i!=s ;i=pre[i] )
map[pre[i]][i]-=sum,map[i][pre[i]]+=sum;
ans+=sum;
}
int main()
{
int i,j,x,y,z;
while (scanf("%d%d",&m,&n)==2)
{
for (i=1;i<=n ;i++ )
for (j=1;j<=n ;j++ )
map[i][j]=0;
for (i=1;i<=m ;i++ )
{
scanf("%d%d%d",&x,&y,&z);
map[x][y]+=z;
}
ans=0;
memset(vis,1,sizeof(vis));
vis[1]=0;
while (bfs(1,n))
{
end(1,n);memset(vis,1,sizeof(vis));vis[1]=0;
}
printf("%d\n",ans);
}
return 0;
}
第一次wa了，看了discuss才知道可能有重邊?。?！又是一個(gè)活生生的例子?。。?！哦耶，網(wǎng)絡(luò)問題，開始啦。