首先，對于無源匯的上下界可行流，常見做法是拆邊：
然后轉換成無下界的模型去做：
即添加源匯s, t，然后將任意一條邊(u, v, l, c)（即u到v,下界l,上界c的邊）拆成三條：
(u, v, 0, c - l), (s, v, 0, l), (u, t, 0, l)
其思想實際就是讓所邊的下界流量的分離出來，作為一條"必要邊"(即如果有可行流，這些容量為下界的邊一定是滿的)，讓其統一流入匯，然后讓源點來提供這樣的流量。
然后在這個網絡上求最大流。看最大流是否 == 所有邊的下界之和。
如果題目已經有了源匯，我們就先連一條(t, s, 0, 無限大)的邊（顯然這不影響流量平衡條件）。這樣就轉換成了前面所說的無源匯的情況，然后求之。
輸出的結果就讓相應原始邊的流量加上他們的下界就可以了（即邊(u, v, 0, c - l)的流量 + l）。
對于有源匯的上下界最大流 可以二分枚舉(t,s)邊的容量下界，判斷是否存在可行流。
對于有源匯的上下界最小流 可以二分枚舉(t,s)邊的容量上界，判斷是否存在可行流。
  SGU194
//就是很裸的一道上下限可行流。
//如果存在可行流要按照邊的輸入順序輸出圖中各邊的流量。
//在判斷完是否可行之后，再把原圖中的流+必要邊就是原圖中的流量了。
//最大流用的ISAP+GAP
#include<iostream>
#define maxn 300
const int inc=1000000000;
using namespace std;
struct edge
{
int u,v,next,c,pre,f,Point;
}e[100000];
int num,rnum;
int head[maxn],rhead[maxn];
int d[maxn];
int numb[maxn];
int start[maxn];
int n,m;
int p[maxn];
int source,sink;
void Init()
{
memset(head,-1,sizeof(head));
memset(rhead,-1,sizeof(rhead));
memset(p,-1,sizeof(p));
num=0;
return ;
}
void BFS()
{
int i,j;
for(i=0;i<n;i++)
{
d[i]=n;
numb[i]=0;
}
int Q[maxn],head(0),tail(0);
d[sink]=0;
numb[0]=1;
Q[++tail]=sink;
while(head<tail)
{
i=Q[++head];
for(j=rhead[i];j!=-1;j=e[j].pre)
{
if(e[j].c==0||d[e[j].u]<n)
continue;
d[e[j].u]=d[i]+1;
numb[d[e[j].u]]++;
Q[++tail]=e[j].u;
}
}
return ;
}
int Augment()
{
int i;
int tmp=inc;
for(i=p[sink];i!=-1;i=p[e[i].u])
{
if(tmp>e[i].c)
tmp=e[i].c;
}
for(i=p[sink];i!=-1;i=p[e[i].u])
{
e[i].c-=tmp;
e[i^1].c+=tmp;
e[i].f+=tmp;
e[i^1].f-=tmp;
}
return tmp;
}
int Retreat(int &i)
{
int tmp,j,mind(n-1);
for(j=head[i];j!=-1;j=e[j].next)
{
if(e[j].c>0&&d[e[j].v]<mind)
mind=d[e[j].v];
}
tmp=d[i];
d[i]=mind+1;
numb[tmp]--;
numb[d[i]]++;
if(i!=source)
i=e[p[i]].u;
return numb[tmp];
}
int maxflow()
{
int flow(0),i,j;
BFS();
for(i=0;i<n;i++)
start[i]=head[i];
i=source;
while(d[source]<n)
{
for(j=start[i];j!=-1;j=e[j].next)
if(e[j].c>0&&d[i]==d[e[j].v]+1)
break;
if(j!=-1)
{
start[i]=j;
p[e[j].v]=j;
i=e[j].v;
if(i==sink)
{
flow+=Augment();
i=source;
}
}
else
{
start[i]=head[i];
if(Retreat(i)==0)
break;
}
}
return flow;
}
void addedge(int a,int b,int c)
{
e[num].next=head[a];
head[a]=num;
e[num].pre=rhead[b];
rhead[b]=num;
e[num].c=c;
e[num].u=a;
e[num++].v=b;
e[num].next=head[b];
head[b]=num;
e[num].pre=rhead[a];
rhead[a]=num;
e[num].u=b;
e[num].v=a;
e[num++].c=0;
return ;
}
int main()
{
int i;
int a,b,c,d;
int nn;
int necessary[100000];
while(scanf("%d%d",&nn,&m)==2)
{
memset(necessary,0,sizeof(necessary));
source=0;
sink=nn+1;
n=nn+2;
Init();
int sum=0;
int first=-1;
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
necessary[i]=c;
addedge(a,b,d-c);
e[num-2].Point=first;
first=num-2;
addedge(source,b,c);
addedge(a,sink,c);
sum+=c;
}
int flow=maxflow();
if(sum!=flow)
printf("NO\n");
else
{
printf("YES\n");
int cnt=1;
for(i=first;i!=-1;i=e[i].Point)
{
necessary[m-cnt+1]+=e[i].f;
cnt++;
}
for(i=1;i<=m;i++)
printf("%d\n",necessary[i]);
}
}
system("pause");
return 0;
}
|