题意:

  给出双向图,求给出两点的流通总流量。

分析:

  网络流中的增广路算法。

代码:

  

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=103;
int g[maxn][maxn],flow[maxn][maxn];
int f[maxn];
int s,t,n;
int bfs()
{
int a[maxn];
int u,v;
memset(flow,0,sizeof(flow));
int flag=0;
while(1)
{
memset(a,0,sizeof(a));
queue<int>q;
a[s]=100000;
q.push(s);
while(!q.empty())
{
u=q.front();
q.pop();
for(v=1;v<=n;v++)
{
if(!a[v]&&g[u][v]-flow[u][v]>0)
{
f[v]=u;
a[v]=a[u]>g[u][v]-flow[u][v]?g[u][v]-flow[u][v]:a[u];
q.push(v);
}
}
}
if(a[t]==0)
break;
for(u=t;u!=s;u=f[u])
{
flow[f[u]][u]+=a[t];
flow[u][f[u]]-=a[t];
}
flag+=a[t];
}
return flag;
}
int main()
{
int c,u,v,cost;
int cas=1;
while(scanf("%d",&n)&&n)
{
scanf("%d%d%d",&s,&t,&c);
memset(g,0,sizeof(g));
while(c--)
{
scanf("%d%d%d",&u,&v,&cost);
g[u][v]+=cost;
g[v][u]=g[u][v];
}
printf("Network %d\n",cas++);
printf("The bandwidth is %d.\n\n",bfs());
}
}
05-08 15:41