poj 2396 Budget--有源汇+有上下界+可行流
[cpp] view plaincopyprint?/*
有源汇 有上下界 求可行流
有源汇可以转化为无源汇:添加一条边t~s (0,0x7fffffff) 就成了无源汇
基本流程是：
构造附加网络(添加新源 新汇 分离必要弧)
求附加网络的最大流
若新源 新汇 相邻的边都是满流，则存在可行流
题意：
有个表格，给出每行的和以及每列的和 还有某些元素的要求
求一个符合条件的表格
添加新的源汇后，分离必要弧(必有一端是新源或新汇，必须满流才有可行流)
这时候有两种(新源ss新汇tt)：
1.添加 (u,v)流量为上下界之差 (ss,v) 和 (u,tt) 的流量都是 下界流量
可以这样理解：(u,v)流量为上下界之差 是因为要改造成下界流量为0的
(ss,v)流量是下界流量 是因为要补充(u,v)中的下界流量，使其直接到v
(u,tt)流量是下界流量 从u之前流过来的流量中，无法通过全部(u,v)，其下界部分通过这条边直接到tt
上面那篇文站就是这样讲的，但是他写的时候用的是第二种
2.添加 (u,v)流量为上下界之差 (ss,u) 和 (u,tt) 的流量都是 流入u的所有下界流量之和 减去 流出u的所有下界流量之和(有图)
这两种方法分别是从 边 点 两个方面进行的
把边或点的下界分离出来，使所有的边或点的下界都为0，转化为普通的最大流问题
下界部分直接由ss提供或直接流向tt
*/
#include<iostream>
#include<string>
using namespace std;
#define N 235
int map[N][N],m,n,s,t,x,y,up[N][N],low[N][N],yu[N],num[N],d[N];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
void ini()
{
memset(low,0,sizeof(low));
memset(map,0,sizeof(map));
memset(yu,0,sizeof(yu));
for(int i=0;i<=m;++i)
for(int j=0;j<=n;++j)
up[i][j]=0x7fffffff;
}
int build()
{
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(low[i][j]>up[i][j]) return 0;
else{
yu[i]-=low[i][j],yu[j+m]+=low[i][j];//这里的m写成了n
map[i][j+m]=up[i][j]-low[i][j];
}
return 1;
}
int sap(int u,int f)
{
if(u==y)//到达终点
return f;
int v,mind=y,last=f,cost;//mind=点数-1 若从0开始，即为最后那个点
for(v=0;v<=y;++v)
{
if(map[u][v]>0)
{
if(d[u]==d[v]+1)
{
cost=sap(v,min(last,map[u][v]));
map[u][v]-=cost;
map[v][u]+=cost;
last-=cost;
if(d[x]>=y+1)
return f-last;
if(last==0)
break;
}
if(d[v]<mind)
mind=d[v];
}
}
if(last==f)
{
--num[d[u]];
if(num[d[u]]==0)
d[x]=y+1;
d[u]=mind+1;
++num[d[u]];
}
return f-last;
}
void limitflow()//
{
int i,j,c=0;//c最大流的流量
x=t+1,y=t+2;//新源 新汇
for(i=s;i<=t;++i)
if(yu[i]>0) map[x][i]=yu[i];//必要弧
else if(yu[i]<0) map[i][y]=-yu[i];//必要弧
map[t][s]=0x7fffffff;//把原图改成无源汇
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for(num[x]=y+1;d[x]<y+1;)//y+1点数
c+=sap(x,0x7fffffff);//用sap求最大流
for(i=s;i<=t;++i)//判断是否满流
if(map[x][i])
{
cout<<"IMPOSSIBLE"<<endl<<endl;
return;
}
for(i=1;i<=m;++i)//输出可行流
{
for(j=1;j<n;++j)
cout<<(up[i][j]-map[i][j+m])<<" ";//上界-未用可增部分
cout<<(up[i][n]-map[i][n+m])<<endl;
}
cout<<endl;
}
int main()
{
int cas,sum1,sum2,i,j,a,b,num,c,f1,f2,t1,t2;
string op;
cin>>cas;
while(cas--)
{
cin>>m>>n;
s=0,t=m+n+1,sum1=sum2=0;
ini();
for(i=1;i<=m;++i) cin>>a,yu[s]-=a,yu[i]+=a,sum1+=a;
for(;i<=m+n;++i) cin>>a,yu[i]-=a,yu[t]+=a,sum2+=a;
cin>>c;
while(c--)//他的处理方法很好
{
cin>>a>>b>>op>>num;
f1=t1=a;
f2=t2=b;
if(a==0)
f1=1,t1=m;
if(b==0)
f2=1,t2=n;
for(i=f1;i<=t1;++i)
for(j=f2;j<=t2;++j)
if(op[0]=='=')
low[i][j]=max(num,low[i][j]),up[i][j]=min(num,up[i][j]);
else if(op[0]=='>')
low[i][j]=max(num+1,low[i][j]);
else if(op[0]=='<')
up[i][j]=min(num-1,up[i][j]);
}
if(sum1==sum2&&build()) limitflow();
else cout<<"IMPOSSIBLE"<<endl<<endl;
}
return 0;
}
/*
有源汇 有上下界 求可行流
有源汇可以转化为无源汇:添加一条边t~s (0,0x7fffffff) 就成了无源汇
基本流程是：
构造附加网络(添加新源 新汇 分离必要弧)
求附加网络的最大流
若新源 新汇 相邻的边都是满流，则存在可行流
题意：
有个表格，给出每行的和以及每列的和 还有某些元素的要求
求一个符合条件的表格
一个比较详细的讲解 http://blog.csdn.net/water_glass/article/details/6823741
添加新的源汇后，分离必要弧(必有一端是新源或新汇，必须满流才有可行流)
这时候有两种(新源ss新汇tt)：
1.添加 (u,v)流量为上下界之差 (ss,v) 和 (u,tt) 的流量都是 下界流量
可以这样理解：(u,v)流量为上下界之差 是因为要改造成下界流量为0的
(ss,v)流量是下界流量 是因为要补充(u,v)中的下界流量，使其直接到v
(u,tt)流量是下界流量 从u之前流过来的流量中，无法通过全部(u,v)，其下界部分通过这条边直接到tt
上面那篇文站就是这样讲的，但是他写的时候用的是第二种
2.添加 (u,v)流量为上下界之差 (ss,u) 和 (u,tt) 的流量都是 流入u的所有下界流量之和 减去 流出u的所有下界流量之和(有图)
这两种方法分别是从 边 点 两个方面进行的
把边或点的下界分离出来，使所有的边或点的下界都为0，转化为普通的最大流问题
下界部分直接由ss提供或直接流向tt
*/
#include<iostream>
#include<string>
using namespace std;
#define N 235
int map[N][N],m,n,s,t,x,y,up[N][N],low[N][N],yu[N],num[N],d[N];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
void ini()
{
memset(low,0,sizeof(low));
memset(map,0,sizeof(map));
memset(yu,0,sizeof(yu));
for(int i=0;i<=m;++i)
for(int j=0;j<=n;++j)
up[i][j]=0x7fffffff;
}
int build()
{
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
if(low[i][j]>up[i][j]) return 0;
else{
yu[i]-=low[i][j],yu[j+m]+=low[i][j];//这里的m写成了n
map[i][j+m]=up[i][j]-low[i][j];
}
return 1;
}
int sap(int u,int f)
{
if(u==y)//到达终点
return f;
int v,mind=y,last=f,cost;//mind=点数-1 若从0开始，即为最后那个点
for(v=0;v<=y;++v)
{
if(map[u][v]>0)
{
if(d[u]==d[v]+1)
{
cost=sap(v,min(last,map[u][v]));
map[u][v]-=cost;
map[v][u]+=cost;
last-=cost;
if(d[x]>=y+1)
return f-last;
if(last==0)
break;
}
if(d[v]<mind)
mind=d[v];
}
}
if(last==f)
{
--num[d[u]];
if(num[d[u]]==0)
d[x]=y+1;
d[u]=mind+1;
++num[d[u]];
}
return f-last;
}
void limitflow()//
{
int i,j,c=0;//c最大流的流量
x=t+1,y=t+2;//新源 新汇
for(i=s;i<=t;++i)
if(yu[i]>0) map[x][i]=yu[i];//必要弧
else if(yu[i]<0) map[i][y]=-yu[i];//必要弧
map[t][s]=0x7fffffff;//把原图改成无源汇
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for(num[x]=y+1;d[x]<y+1;)//y+1点数
c+=sap(x,0x7fffffff);//用sap求最大流
for(i=s;i<=t;++i)//判断是否满流
if(map[x][i])
{
cout<<"IMPOSSIBLE"<<endl<<endl;
return;
}
for(i=1;i<=m;++i)//输出可行流
{
for(j=1;j<n;++j)
cout<<(up[i][j]-map[i][j+m])<<" ";//上界-未用可增部分
cout<<(up[i][n]-map[i][n+m])<<endl;
}
cout<<endl;
}
int main()
{
int cas,sum1,sum2,i,j,a,b,num,c,f1,f2,t1,t2;
string op;
cin>>cas;
while(cas--)
{
cin>>m>>n;
s=0,t=m+n+1,sum1=sum2=0;
ini();
for(i=1;i<=m;++i) cin>>a,yu[s]-=a,yu[i]+=a,sum1+=a;
for(;i<=m+n;++i) cin>>a,yu[i]-=a,yu[t]+=a,sum2+=a;
cin>>c;
while(c--)//他的处理方法很好
{
cin>>a>>b>>op>>num;
f1=t1=a;
f2=t2=b;
if(a==0)
f1=1,t1=m;
if(b==0)
f2=1,t2=n;
for(i=f1;i<=t1;++i)
for(j=f2;j<=t2;++j)
if(op[0]=='=')
low[i][j]=max(num,low[i][j]),up[i][j]=min(num,up[i][j]);
else if(op[0]=='>')
low[i][j]=max(num+1,low[i][j]);
else if(op[0]=='<')
up[i][j]=min(num-1,up[i][j]);
}
if(sum1==sum2&&build()) limitflow();
else cout<<"IMPOSSIBLE"<<endl<<endl;
}
return 0;
}
作者：qq172108805
