HDU 4888 (网络流）

Poroblem Redraw Beautiful Drawings （HDU4888）

题目大意

　　一个n行m列的矩形，只能填0~k的数字。

　　给定各行各列的数字和，判定有无合法的方案数。一解给出方案，多解输出给定字符串。

解题分析

　　一个经典的网络流建图。

　　由S向行连流量为该行数字和的边，由列向T连流量为该列数字和的边，从行向列连流量为k的边。

　　若满流说明有解。

　　在残余网络中从每个点开始dfs，若找到一个点数大于2的环，说明有多解。

参考程序

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <queue>
  6 using namespace std;
  7 
  8 #define eps 1e-8
  9 #define INF 2000000000
 10 #define V 2000
 11 #define E 1000000
 12 int n,m,k,ans,dis[V],S,T,cnt,vis[V],flag;
 13 
 14 struct line{
 15     int u,v,c,nt;
 16 }eg[E];
 17 int lt[V],sum=1,map[V][V];
 18 
 19 void adt(int u,int v,int c){
 20     eg[++sum].u=u; eg[sum].v=v; eg[sum].c=c; eg[sum].nt=lt[u]; lt[u]=sum;
 21 }
 22 
 23 void add(int u,int v,int c){
 24     adt(u,v,c); adt(v,u,0);
 25 }
 26 
 27 void init(){
 28     memset(lt,0,sizeof(lt));
 29     sum=1; ans=0; cnt=0;
 30 
 31     S=0; T=n+m+1;
 32     for (int i=1;i<=n;i++)
 33         for (int j=1;j<=m;j++)
 34         {
 35             add(i,j+n,k);
 36             map[i][j]=sum;
 37         }
 38     for (int i=1;i<=n;i++) 
 39     {
 40         int x;
 41         scanf("%d",&x);
 42         add(S,i,x);
 43     }
 44     for (int i=1;i<=m;i++) 
 45     {
 46         int x;
 47         scanf("%d",&x);
 48         add(i+n,T,x);
 49         cnt+=x;
 50     }
 51 }
 52 
 53 bool bfs(){
 54     memset(dis,0,sizeof(dis));
 55     dis[S]=1;
 56     queue<int> Q;
 57     Q.push(S);
 58     while (!Q.empty()){
 59         int u=Q.front();
 60         Q.pop();
 61         for (int i=lt[u];i;i=eg[i].nt){
 62             int v=eg[i].v;
 63             if (eg[i].c && !dis[v]){
 64                 dis[v]=dis[u]+1;
 65                 Q.push(v);
 66             }
 67         }
 68     }
 69     return dis[T]>0;
 70 }
 71 
 72 int dfs(int u,int flow){
 73     if (u==T) return flow;
 74     int res=0,f;
 75     for (int i=lt[u];i;i=eg[i].nt){
 76         int v=eg[i].v;
 77         if (eg[i].c&&dis[v]==dis[u]+1){
 78             f=dfs(v,min(flow-res,eg[i].c));
 79             res+=f;
 80             eg[i].c-=f;
 81             eg[i ^ 1].c+=f;
 82             if (flow==res) break;
 83         }
 84     }
 85     if (!res) dis[u]=-1;
 86     return res;
 87 }
 88 
 89 int dinic(){
 90     int sum=0;
 91     while (bfs()) sum+=dfs(S,INF);
 92     return sum;
 93 }
 94 
 95 void dfs_1(int u,int fa,int rt){
 96     vis[u]=1;
 97     if (flag) return;
 98     for (int i=lt[u];i;i=eg[i].nt){
 99         int v=eg[i].v;
100         if (eg[i].c==0 || v==fa) continue;
101         if (v==rt) {
102             flag=1;
103             return;
104         }
105         if (!vis[v]){
106              dfs_1(v,u,rt);
107         }
108     }
109 }
110 
111 int main(){
112 
113     while (~scanf("%d %d %d",&n,&m,&k)){
114           init();  
115           int x=dinic();
116           if (x!=cnt) { printf("Impossible
"); continue; }
117           for (int i=0;i<=T;i++){
118             memset(vis,0,sizeof(vis));
119               flag=0;
120               dfs_1(i,0,i);
121               if (flag) break;
122        }
123           if (flag) { printf("Not Unique
"); continue;}
124         printf("Unique
");
125         for (int i=1;i<=n;i++)
126             for (int j=1;j<=m;j++){
127                 if (j==m) printf("%d
",eg[map[i][j]].c); else printf("%d ",eg[map[i][j]].c);
128             }
129     }    
130 }

View Code