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();

补充：软件开发 , C++ ,