poj 2396 Budget--有源汇+有上下界+可行流
/*有源汇 有上下界 求可行流有源汇可以转化为无源汇:添加一条边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 235int 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写成了nmap[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;}