UVA 11082 - Matrix Decompressing

UVA 11082 - Matrix Decompressing

題目概述:經典入門書p11-29

給一個n*m矩陣的每一行與每一列的加總。求任一種原矩陣。

思路:

這題想破頭也想不到用flow來解QQ

待補。

//By SCJ

//#include<iostream>

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

#define INF 1000000000

struct Edge{

   int to,cap,rev;

};

vector<Edge> G[405];//S=0,X->1~n,Y->n+1~n+m,T=n+m+1

void add_Edge(int from,int to,int cap)

{

   G[from].push_back({to,cap,G[to].size()});

   G[to].push_back({from,0,G[from].size()-1});

}

int n,m,S,T,A[21],B[21],ans[21][21];

bool used[405];

int dfs(int u,int f)

{

   if(u==T) return f;

   used[u]=1;

   for(Edge &e:G[u])

   {

       if(used[e.to]||e.cap<=0) continue;

       int d=dfs(e.to,min(f,e.cap));

       if(d){

           e.cap-=d;

           G[e.to][e.rev].cap+=d;

           return d;

       }

   }

   return 0;

}

int max_flow()

{

   int res=0;

   while(1)

   {

       memset(used,0,sizeof(used));

       int d=dfs(S,INF);

       if(d==0) break;

       res+=d;

   }

   return res+n*m;

}

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

   int ca;cin>>ca;

   for(int no=1;no<=ca;++no)

   {

       if(no>1) cout<<endl;

       cin>>n>>m;S=0;T=n+m+1;

       for(int i=1;i<=n;++i) cin>>A[i];

       for(int i=1;i<=m;++i) cin>>B[i];

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

           add_Edge(S,i,A[i]-A[i-1]-m);

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

           add_Edge(n+i,T,B[i]-B[i-1]-n);

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

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

               add_Edge(i,n+j,19);

       int tp=max_flow();

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

       {

           for(Edge e:G[i])

           {

               if(e.to<=n) continue;

               //cout<<i<<' '<<e.to-n<<' '<<19-e.cap+1<<endl;

               ans[i][e.to-n]=19-e.cap+1;

           }

       }

       cout<<"Matrix "<<no<<endl;

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

       {

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

           {

               if(j>1) cout<<' ';

               cout<<ans[i][j];

           }

           cout<<endl;

       }

       for(int i=0;i<=T;++i) G[i].clear();

   }

}