最近在搞網絡流，剛研究完幾個求最大流的基本算法，今天研究了一下有上下界的可行流問題，參考了大牛ADN.cn的圖論總結，算法倒不是很難，代碼也很快就寫好了，只是不知道原因，就是不能AC，郁悶我一晚上。。。在SGU上 只能過9組數據，也不知道被什么BT的數據給卡住了，希望大牛們能給我點指點。 我用的方法是添加兩個附加源匯，用dinic算法求最大流，如果源匯上的邊滿流，則說明有可行流，輸出每條邊的流量，否則輸出NO.
下面是我WA掉的代碼：
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cassert>
using namespace std;
#define MAX 210
#define MAXINT 999999999
struct pipe
{
__int64 a;
__int64 b;
__int64 l;
__int64 r;
}mypipe[MAX*1000];
__int64 n,m;
__int64 graph[MAX][MAX];
__int64 d[MAX];
__int64 ans=0;
__int64 min(__int64 a,__int64 b)
{
if(a<b)
return a;
else
return b;
}
void init()
{
__int64 i;
memset(graph,0,sizeof(graph));
for(i=1;i<=m;i++)
{
scanf("%I64d%I64d%I64d%I64d",&mypipe[i].a,&mypipe[i].b,&mypipe[i].l,&mypipe[i].r);
graph[mypipe[i].a][mypipe[i].b]+=mypipe[i].r-mypipe[i].l;
graph[mypipe[i].a][n+2]+=mypipe[i].l;
graph[n+1][mypipe[i].b]+=mypipe[i].l;
}
}
bool build(__int64 n)
{
memset(d,0,sizeof(d));
bool visit[MAX]={0};
__int64 myqueue[MAX*MAX]={0};
__int64 front=1,rear=1;
myqueue[rear]=n-1;visit[myqueue[front]]=true;
while(front<=rear)
{
__int64 i;
for(i=1;i<=n;i++)
{
if((!visit[i])&&graph[myqueue[front]][i]>0)
{
rear++;
myqueue[rear]=i;
d[i]=d[myqueue[front]]+1;
visit[i]=true;
}
}
front++;
}
if(visit[n]==true)
return true;
else
return false;
}
__int64 dinic(__int64 v,__int64 sum,__int64 n)
{
if(v==n)
return sum;
__int64 ret=0;
__int64 t;
__int64 i;
for(i=1;i<=n;i++)
{
if(d[i]==d[v]+1&&graph[v][i]>0)
{
t=dinic(i,min(graph[v][i],sum)-ret,n);
graph[v][i]-=t;
graph[i][v]+=t;
ret+=t;
}
}
return ret;
}
int main()
{
__int64 j;
__int64 flag=0;
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
init();
flag=0;
while(build(n+2))
{
dinic(n+1,MAXINT,n+2);
}
for(j=1;j<=n;j++)
{
if(graph[j][n+2]!=0||graph[n+1][j]!=0)
{
flag=1;
break;
}
}
if(flag==1)
{
printf("NO\n\n");
continue;
}
else
{
printf("YES\n");
for(j=1;j<=m;j++)
{
printf("%I64d\n",graph[mypipe[j].b][mypipe[j].a]+mypipe[j].l);
}
printf("\n");
}
}
return 0;
}