poj 2396 Budget

一个m行n列的矩阵，给出每行每列中元素的和，以及对一些格子的大小限制，求一个可行方案，输出矩阵。

大小限制形如：严格大于i，严格小于i，等于i。

1<=m<=200.1<=n<=20.

有源汇上下界可行流。

将每一行作为一个点，每一列作为一个点。

源点向每个行点连一条上下界均为该行和的边。

每个列点向汇点连一条上下界均为该列和的边。

每个行点向各列点连一条上下界为该行该列对应点的上下限的边。

然后做一遍有源汇上下界可行流就好了。

（汇点向源点连一条上界为正无穷下界为0的边，就转成无源汇上下界可行流啦！

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 using namespace std;

 const int dian=;

 const int bian=;

 const int INF=0x3f3f3f3f;

 int h[dian],nxt[bian],ver[bian],val[bian],ch[dian],cr[dian];

 int sx[][],xx[][],bh[][],in[dian],out[dian];

 int n,m,aa,bb,cc,tot,num,flag,summ;

 int S,T,SS,TT;

 char la[];

 void add(int a,int b,int c,int d){

     tot++;ver[tot]=b;val[tot]=d-c;nxt[tot]=h[a];h[a]=tot;

     tot++;ver[tot]=a;val[tot]=;nxt[tot]=h[b];h[b]=tot;

     in[b]+=c;

     out[a]+=c;

 }

 bool tell(){

     memset(ch,-,sizeof(ch));

     queue<int>q;

     q.push(S);

     ch[S]=;

     while(!q.empty()){

         int t=q.front();

         q.pop();

         for(int i=h[t];i;i=nxt[i])

             if(ch[ver[i]]==-&&val[i]){

                 ch[ver[i]]=ch[t]+;

                 q.push(ver[i]);

             }

     }

     return ch[T]!=-;

 }

 int zeng(int a,int b){

     if(a==T)

         return b;

     int r=;

     for(int i=cr[a];i&&b>r;i=nxt[i])

         if(ch[ver[i]]==ch[a]+&&val[i]){

             int t=zeng(ver[i],min(b-r,val[i]));

             val[i]-=t,r+=t,val[i^]+=t;

             if(val[i])

                 cr[a]=i;

         }

     if(!r)

         ch[a]=-;

     return r;

 }

 int dinic(){

     int r=,t;

     while(tell()){

         for(int i=;i<=n+m+;i++)

             cr[i]=h[i];

         while(t=zeng(S,INF))

             r+=t;

     }

     return r;

 }

 int main(){

     int cas;

     scanf("%d",&cas);

     while(cas--){

         memset(h,,sizeof(h));

         memset(nxt,,sizeof(nxt));

         memset(sx,0x3f,sizeof(sx));

         memset(xx,,sizeof(xx));

         memset(in,,sizeof(in));

         memset(out,,sizeof(out));

         tot=;

         summ=;

         scanf("%d%d",&n,&m);

         SS=n+m+,TT=n+m+,S=n+m+,T=n+m+;

         for(int i=;i<=n;i++){

             scanf("%d",&aa);

             add(SS,i,aa,aa);

         }

         for(int i=;i<=m;i++){

             scanf("%d",&aa);

             add(n+i,TT,aa,aa);

         }

         scanf("%d",&num);

         while(num--){

             scanf("%d%d%s%d",&aa,&bb,la,&cc);

             if(!aa&&!bb){

                 for(int i=;i<=n;i++)

                     for(int j=;j<=m;j++){

                         if(la[]=='<')

                             sx[i][j]=min(sx[i][j],cc-);

                         else if(la[]=='>')

                             xx[i][j]=max(xx[i][j],cc+);

                         else{

                             sx[i][j]=min(sx[i][j],cc);

                             xx[i][j]=max(xx[i][j],cc);

                         }

                     }

             }

             else if(!aa){

                 for(int i=;i<=n;i++){

                     if(la[]=='<')

                         sx[i][bb]=min(sx[i][bb],cc-);

                     else if(la[]=='>')

                         xx[i][bb]=max(xx[i][bb],cc+);

                     else{

                         sx[i][bb]=min(sx[i][bb],cc);

                         xx[i][bb]=max(xx[i][bb],cc);

                     }

                 }

             }

             else if(!bb){

                 for(int i=;i<=m;i++){

                     if(la[]=='<')

                         sx[aa][i]=min(sx[aa][i],cc-);

                     else if(la[]=='>')

                         xx[aa][i]=max(xx[aa][i],cc+);

                     else{

                         sx[aa][i]=min(sx[aa][i],cc);

                         xx[aa][i]=max(xx[aa][i],cc);

                     }

                 }

                 for(int i=;i<=n;i++){

                     if(la[]=='<')

                         sx[i][bb]=min(sx[i][bb],cc-);

                     else if(la[]=='>')

                         xx[i][bb]=max(xx[i][bb],cc+);

                     else{

                         sx[i][bb]=min(sx[i][bb],cc);

                         xx[i][bb]=max(xx[i][bb],cc);

                     }

                 }

             }

             else{

                 if(la[]=='<')

                     sx[aa][bb]=min(sx[aa][bb],cc-);

                 else if(la[]=='>')

                     xx[aa][bb]=max(xx[aa][bb],cc+);

                 else{

                     sx[aa][bb]=min(sx[aa][bb],cc);

                     xx[aa][bb]=max(xx[aa][bb],cc);

                 }

             }

         }

         flag=;

         for(int i=;i<=n;i++){

             for(int j=;j<=m;j++){

                 if(sx[i][j]>=xx[i][j]){

                     bh[i][j]=tot+;

                     add(i,n+j,xx[i][j],sx[i][j]);

                 }

                 else{

                     flag=;

                     break;

                 }

             }

             if(flag)

                 break;

         }

         if(flag){

             puts("IMPOSSIBLE");

             puts("");

             continue;

         }

         add(TT,SS,,INF);

         for(int i=;i<=TT;i++){

             if(in[i]-out[i]>)

                 add(S,i,,in[i]-out[i]);

             else if(out[i]-in[i]>){

                 add(i,T,,out[i]-in[i]);

                 summ=summ+out[i]-in[i];

             }

         }

         if(dinic()!=summ){

             puts("IMPOSSIBLE");

             puts("");

             continue;

         }

         for(int i=;i<=n;i++){

             for(int j=;j<=m;j++)

                 printf("%d ",xx[i][j]+val[bh[i][j]^]);

             puts("");

         }

         puts("");

     }

     return ;

 }

注意：

一个格子可能有多重限制，上限取min下限取max。

上限可能小于下限要判掉。

每组数据输出间有空行（不加也没事？）。

如果wa了就再读一遍建图，不行就再读一遍。

巴特西

poj 2396 Budget

最新文章

热门文章