首先，对于无源汇的上下界可行流，常见做法是拆边：
然后转换成无下界的模型去做：
即添加源汇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;
}
|