poj 2396 Budget--有源汇+有上下界+可行流

来源:岁月联盟 编辑:exp 时间:2012-07-25

/
[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