[网络流最大流经典][uva 11082][矩阵解压]-白红宇

[网络流最大流经典][uva 11082][矩阵解压]

阅读量：6249 次

发布时间：2019-06-22

本文共 2179 字，大约阅读时间需要 7 分钟。

题目大意

这里写图片描述

分析

这里写图片描述

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #define oo 0x13131313using namespace std;const int MAXN=200+5;const int MAXM=2000;const int INF=0x3f3f3f3f;struct Edge{ int to,next,cap,flow; void get(int a,int b,int c,int d) { to=a;next=b;cap=c;flow=d; }}edge[MAXM];int tol;int head[MAXN];int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];void init(){ tol=0; memset(head,-1,sizeof(head));}//单向图三个参数，无向图四个参数void addedge(int u,int v,int w,int rw=0){ edge[tol].get(v,head[u],w,0);head[u]=tol++; edge[tol].get(u,head[v],rw,0);head[v]=tol++;}int sap(int start,int end,int N){ memset(gap,0,sizeof(gap)); memset(dep,0,sizeof(dep)); memcpy(cur,head,sizeof(head)); int u=start; pre[u]=-1; gap[0]=N; int ans=0; while(dep[start]
              
               edge[i].cap-edge[i].flow) Min=edge[i].cap-edge[i].flow; for(int i=pre[u];i!=-1;i=pre[edge[i^1].to]) { edge[i].flow+=Min; edge[i^1].flow-=Min; } u = start; ans+=Min; continue; } bool flag=false; int v; for(int i=cur[u];i !=-1;i=edge[i].next) { v=edge[i].to; if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]) { flag=true; cur[u]=pre[v]=i; break; } } if(flag) { u=v; continue; } int Min=N; for(int i=head[u];i!=-1;i=edge[i].next) if(edge[i].cap-edge[i].flow&&dep[edge[i].to]
               
                >R>>C; for(int i=1;i<=R;i++) scanf("%d",&A[i]); for(int i=1;i<=C;i++) scanf("%d",&B[i]); for(int i=R;i>=1;i--) { A[i]=A[i]-A[i-1]; sum=sum+A[i]; } for(int i=C;i>=1;i--) B[i]=B[i]-B[i-1];}void solve(){ int S=0,T=R+C+1; //S-> for(int i=1;i<=R;i++) { addedge(S,i,A[i]-C); } //->T for(int i=1;i<=C;i++) { addedge(R+i,T,B[i]-R); } for(int i=1;i<=R;i++) for(int j=1;j<=C;j++) { addedge(i,R+j,19); }}int main(){// freopen("a.in","r",stdin); int T; cin>>T; int CASE=0; while(T--) { printf("Matrix %d\n",++CASE); input(); solve(); int k=sap(0,R+C+1,R+C+2); for(int i=1;i<=R;i++) { for(int p=head[i];p!=-1;p=edge[p].next) { ANS[i][edge[p].to-R]=edge[p].flow+1; } } for(int i=1;i<=R;i++) { for(int j=1;j<=C;j++) { printf("%d",ANS[i][j]); if(j!=C) printf(" "); } printf("\n"); } printf("\n"); }}