关于最大流－最小割算法

NissanPineapple 2005-12-20 10:43:57

各位算法高手，请问有没有对网络流图求最大流－最小割的算法程序啊？
高分求教！
谢谢了！

...全文

282 1 打赏收藏转发到动态举报

写回复

用AI写文章

1 条回复

切换为时间正序

请发表友善的回复…

发表回复

ShowLovE 2005-12-20

打赏
举报

/**********************
最大流算法
***********************/
#include<stdio.h>
#include<limits.h>
#define abs(i) ((i)<0)?(-(i)):(i)
#define N 100
long limits[N][N],last[N],flow[N][N],n,m;
//limits数组记录容量, flow记录流量
// last记录某一点在增广路上的前趋:设为 i, 则正向弧标为 i, 反向弧标为-i
int Init();
int main()
{
long i,j,k,used[N],v1,v2,cost,s,t,delta,sum; //delta可改进的流量
while((scanf("%ld%ld",&n,&m))!=EOF) //输入顶点数, 边数
{
Init();
s=1,t=n; // s为源点, t为汇点
for(i=0;i<m;i++)
{
scanf("%ld%ld%ld",&v1,&v2,&cost); //输入边及其相应的流量
limits[v1][v2]=cost;
}
while(1)
{
for(i=1;i<=n;i++)used[i]=0,last[i]=0;
last[s]=INT_MAX;
while(last[t]==0)
{
for(i=1;i<=n;i++)
if(last[i]&&!used[i])break;
//找一个已标号但未使用过的点
if(i>n)break;
for(j=1;j<=n;j++)
if(!last[j])
{
if(flow[i][j]<limits[i][j]) last[j]=i;
if(flow[j][i])last[j]=-i;
//找到点 i 的一个未被标号的后继
}
used[i]=1;
} /*程序的核心:增广路的求法*/
if(last[n]==0)break; //汇点未被标号, 则说明无增广路, 退出循环
for(i=n,delta=INT_MAX,k=INT_MAX;i!=1;)
{
j=last[i]; //找可调整的流量
if(j>0)k=limits[j][i]-flow[j][i];
else k=flow[i][j];
if(k<delta)delta=k;
i=abs(j);
}
for(i=n;i!=1;)
{
j=last[i];
if(j<0)flow[i][j]-=delta;
else flow[j][i]+=delta;
i=abs(j);
} //调整流量, 使其满足流量图的性质
}
for(i=1,sum=0;i<=n;i++)
{
if(flow[i][n])sum+=flow[i][n];
if(flow[n][i])sum-=flow[n][i];
} // 求最大流
printf("%ld\n",sum); //输出
}
return 0;
}
int Init()
{
long i,j;
for(i=1;i<=n;i++)
for(j=i;j<n;j++)
{
limits[i][j]=limits[j][i]=0;
flow[i][j]=flow[j][i]=0; //初始化流量, 容量为 0
}
return 0;
}