POJ 2396 Budget 有上下界的网络流 - c++编程基础

题意：给出一个表格，给出每行的总值，每列的总值，并给出一些条件，给出某格或某行某列最大值，最小值或本身的值。问是存在这样一个表格，并输出没格的数量。

思路：建图还是比较好想的，建一个源点，一个汇点，M行是M个结点，N列是N个结点，每个行结点向所有列结点存在路径。下界的问题通过建立超级源点，超级汇点来考虑。

（不得不说这道题真是麻烦，太过麻烦稠密的图，还是用邻接矩阵比较好。）

参考资料：百度文库

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include
         #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #define PI acos(-1.0) #define maxn 250 #define INF 1000000000 #define mem(a,b) memset(a,b,sizeof(a)) typedef long long ll; using namespace std; int M[maxn][maxn],Hlim[maxn][maxn],Llim[maxn][maxn],rr[maxn],cc[maxn],ou[maxn],in[maxn],flow[maxn][maxn]; int src,sink,row,col,tt; int a,b,c; char ss; bool vis[maxn]; int dist[maxn]; void bfs(int n) { mem(dist,0); mem(vis,0); queue 
                
                  que; vis[src]=1; que.push(src); while(!que.empty()) { int t=que.front(); que.pop(); for(int i=0; i<=n; i++) if(!vis[i]&&M[t][i]>0) { que.push(i); dist[i]=dist[t]+1; vis[i]=1; } } return; } int init() { mem(Hlim,0); mem(M,0); mem(Llim,0); mem(ou,0); mem(in,0); mem(flow,0); return 0; } int dfs(int u,int del,int n) { if(u==sink) return del; int ret=del; for(int i=0; i<=n; i++) { if(dist[i]==dist[u]+1&&M[u][i]>0) { int d=dfs(i,min(M[u][i],del),n); M[u][i]-=d; M[i][u]+=d; flow[u][i]+=d; flow[i][u]-=d; del-=d; } } return ret-del; } int maxflow(int n) { int ans=0; while(1) { bfs(n); if(!vis[sink]) return ans; ans+=dfs(src,INF,n); } } int main() { int tot; scanf(%d,&tot); while(tot--) { init(); scanf(%d%d,&row,&col); for(int i=1; i<=row; i++) scanf(%d,&rr[i]); for(int i=1; i<=col; i++) scanf(%d,&cc[i]); for(int i=1; i<=row; i++) for(int j=1+row; j<=col+row; j++) Hlim[i][j]=INF; scanf(%d,&tt); while(tt--) { scanf(%d%d %c %d,&a,&b,&ss,&c); if(a==0&&b!=0) { if(ss=='=') for(int i=1; i<=row; i++) Hlim[i][b+row]=Llim[i][b+row]=c; else if(ss=='<') for(int i=1; i<=row; i++) Hlim[i][b+row]=min(c-1,Hlim[i][b+row]); else if(ss=='>') for(int i=1; i<=row; i++) Llim[i][b+row]=max(c+1,Llim[i][b+row]); } else if(a!=0&&b==0) { if(ss=='=') for(int i=1; i<=col; i++) Hlim[a][i+row]=Llim[a][i+row]=c; else if(ss=='<') for(int i=1; i<=col; i++) Hlim[a][i+row]=min(c-1,Hlim[a][i+row]); else if(ss=='>') for(int i=1; i<=col; i++) Llim[a][i+row]=max(c+1,Llim[a][i+row]); } else if(a&&b) { if(ss=='=') Hlim[a][b+row]=Llim[a][b+row]=c; else if(ss=='<') Hlim[a][b+row]=min(c-1,Hlim[a][b+row]); else if(ss=='>') Llim[a][b+row]=max(c+1,Llim[a][b+row]); } else if(a==0&&b==0) { for(int i=1; i<=row; i++) { for(int j=1+row; j<=row+col; j++) { if(ss=='=') Hlim[i][j]=Llim[i][j]=c; else if(ss=='<') Hlim[i][j]=min(c-1,Hlim[i][j]); else if(ss=='>') Llim[i][j]=max(c+1,Llim[i][j]); } } } } int s=0,t=row+col+1; for(int i=1; i<=row; i++) Hlim[s][i]=Llim[s][i]=rr[i]; for(int i=1+row; i<=row+col; i++) Hlim[i][t]=Llim[i][t]=cc[i-row]; src=col+row+2,sink=col+row+3; int sum=0; for(int i=0; i<=t; i++) { for(int j=0; j<=t; j++) { M[i][j]=Hlim[i][j]-Llim[i][j]; ou[i]+=Llim[i][j]; in[j]+=Llim[i][j]; sum+=Llim[i][j]; } } for(int i=0; i<=t; i++) { M[src][i]=in[i]; M[i][sink]=ou[i]; } M[t][s]=INF; int res=maxflow(sink),res2; if(res!=sum) { printf(IMPOSSIBLE ); continue; } else { M[t][s]=0; src=0,sink=col+row+1; res2=maxflow(sink); for(int i=1; i<=row; i++) { for(int j=1; j<=col; j++) { if(j==1) printf(%d,flow[i][1+row]+Llim[i][1+row]); else printf( %d,flow[i][j+row]+Llim[i][j+row]); } printf( ); } } } }