/**//*
sap+gap优化,采用邻接矩正
时间复杂度:O(mn^2)
*/
#include<iostream>
#include<queue>
using namespace std;
const int msize=205; //最大顶点数
const int inf=0x7fffffff;
int dis[msize]; //标号
int r[msize][msize]; //残留网络,初始为原图
int num[msize]; //num[i]表示标号为i的顶点数有多少
int pre[msize];
int n,m,src,des; //n个顶点,m条边,源点src,汇点des
void rev_bfs() //反向bfs计算标号,汇点des标号为0
{
int i,k;
for(i=1;i<=n;i++)
{
dis[i]=n;
num[i]=0;
}
queue<int> q;
q.push(des);
dis[des]=0;
num[0]=1;
while(!q.empty())
{
k=q.front();
q.pop();
for(i=1;i<=n;i++)
{
if(dis[i]==n&&r[i][k]>0)
{
dis[i]=dis[k]+1;
q.push(i);
num[dis[i]]++;
}
}
}
}
int findArc(int i)
{
for(int j=1;j<=n;j++)
{
if(r[i][j]>0&&dis[i]==dis[j]+1)
return j;
}
return -1;
}
int reLable(int i)
{
int mindis=n;
for(int j=1;j<=n;j++)
{
if(r[i][j]>0)
mindis=mindis<dis[j]? mindis:dis[j];
}
return mindis;
}
int maxFlow()
{
rev_bfs();
int totalflow=0, i=src, j, k;
int d; //增量
pre[src]=-1;
while(dis[src]<n)
{
j=findArc(i);
if(j>=0)
{
pre[j]=i;
i=j;
if(i==des)
{
d=inf;
for(k=des;k!=src;k=pre[k])
d=d<r[pre[k]][k]? d:r[pre[k]][k];
for(k=des;k!=src;k=pre[k])
{
r[pre[k]][k]-=d;
r[k][pre[k]]+=d;
}
totalflow+=d;
i=src;
}
}
else
{
--num[dis[i]];
if(0==num[dis[i]]) return totalflow;
int x=reLable(i);
dis[i]=x+1;
num[dis[i]]++;
if(i!=src) i=pre[i];
}
}
return totalflow;
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
int i;
int u,v,w;
memset(r,0,sizeof(r));
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&v,&w);
r[u][v]+=w;
}
src=1;
des=n;
printf("%d\n",maxFlow());
}
return 0;
}
posted on 2011-05-10 13:12
wuxu 阅读(471)
评论(0) 编辑 收藏 引用 所属分类:
图论