基本思路：每次使用SPFA求出一条可增广流的最短路，对最短路上的流进行增流；重复上述过程，直至不存在可增广路。
以下是我的代码，仅供参考：
#include<stdio.h>
#define maxn 507
#define INF 200000007
FILE *fin=fopen("data.in","r"),*fout=fopen("data.out","w");
typedef struct
{
long count,front,rear,item[maxn];
}queue;
void Clear(queue &q)
{
q.count=0;q.front=0;q.rear=-1;
}
void Push(queue &q,long x)
{
q.count++;q.rear++;
if(q.rear>=maxn) q.rear=0;
q.item[q.rear]=x;
}
void Pop(queue &q,long &x)
{
q.count--;x=q.item[q.front];
q.front++;
if(q.front>=maxn) q.front=0;
}
bool Empty(queue &q)
{
return (q.count==0);
}
long n,m,cap[maxn][maxn],cost[maxn][maxn];
long s,t,minc,maxf,flow[maxn][maxn];
long min(long a,long b)
{return (a<b?a:b);}
void input()
{
fscanf(fin,"%ld%ld",&n,&m);
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
{
cap[i][j]=0;cost[i][j]=INF;
}
for(long i=1;i<=m;i++)
{
long a,b,c,d;
fscanf(fin,"%ld%ld%ld%ld",&a,&b,&c,&d);
cap[a][b]=c;cost[a][b]=d;
}
}
void Mincost_Maxflow()
{
long tmp,d[maxn],father[maxn];
bool inq[maxn];
queue q;Clear(q);
s=1;t=n;
for(long i=1;i<=n;i++)
for(long j=1;j<=n;j++)
flow[i][j]=0;
minc=0;maxf=0;
while(true)
{
for(long i=1;i<=n;i++)
{
d[i]=(i==s?0:INF);
father[i]=0;
inq[i]=false;
}
d[s]=0;Push(q,s);inq[s]=true;
while(!Empty(q))
{
long i;Pop(q,i);inq[i]=false;
for(long j=1;j<=n;j++)
if(cap[i][j]>flow[i][j]&&cost[i][j]<INF&&d[i]+cost[i][j]<d[j])
{
d[j]=d[i]+cost[i][j];
father[j]=i;
if(!inq[j])
{Push(q,j);inq[j]=true;}
}
}
if(d[t]>=INF) break;
tmp=INF;
for(long i=t;i!=s;i=father[i]) tmp=min(tmp,cap[father[i]][i]-flow[father[i]][i]);
for(long i=t;i!=s;i=father[i])
{
flow[father[i]][i]+=tmp;
flow[i][father[i]]-=tmp;
}
minc+=tmp*d[t];
maxf+=tmp;
}
}
void output()
{
fprintf(fout,"Mincost := %ld\nMaxflow := %ld\n",minc,maxf);
}
int main()
{
input();
Mincost_Maxflow();
output();
return 0;
}
posted on 2010-04-01 23:04
lee1r 阅读(1226)
评论(0) 编辑 收藏 引用 所属分类:
算法与数据结构