hdu4888 Redraw Beautiful Drawings 最大流+判环

2020-12-13 05:57

阅读：490

标签：des style blog http color java os io

hdu4888

Redraw Beautiful Drawings

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 2007 Accepted Submission(s): 447

Problem Description

Alice and Bob are playing together. Alice is crazy about art and she has visited many museums around the world. She has a good memory and she can remember all drawings she has seen.
Today Alice designs a game using these drawings in her memory. First, she matches K+1 colors appears in the picture to K+1 different integers(from 0 to K). After that, she slices the drawing into grids and there are N rows and M columns. Each grid has an integer on it(from 0 to K) representing the color on the corresponding position in the original drawing. Alice wants to share the wonderful drawings with Bob and she tells Bob the size of the drawing, the number of different colors, and the sum of integers on each row and each column. Bob has to redraw the drawing with Alice‘s information. Unfortunately, somtimes, the information Alice offers is wrong because of Alice‘s poor math. And sometimes, Bob can work out multiple different drawings using the information Alice provides. Bob gets confused and he needs your help. You have to tell Bob if Alice‘s information is right and if her information is right you should also tell Bob whether he can get a unique drawing.

Input

The input contains mutiple testcases.
For each testcase, the first line contains three integers N(1 ≤ N ≤ 400) , M(1 ≤ M ≤ 400) and K(1 ≤ K ≤ 40). N integers are given in the second line representing the sum of N rows. M integers are given in the third line representing the sum of M columns.
The input is terminated by EOF.

Output

For each testcase, if there is no solution for Bob, output "Impossible" in one line(without the quotation mark); if there is only one solution for Bob, output "Unique" in one line(without the quotation mark) and output an N * M matrix in the following N lines representing Bob‘s unique solution; if there are many ways for Bob to redraw the drawing, output "Not Unique" in one line(without the quotation mark).

Sample Input

2 2 4 4 2 4 2 4 2 2 2 2 5 0 5 4 1 4 3 9 1 2 3 3

Sample Output

Not Unique Impossible Unique 1 2 3 3

Author

Fudan University

Source

2014 Multi-University Training Contest 3

Recommend

We have carefully selected several similar problems for you: 4910 4909 4908 4907 4906

大意：n*m的矩阵，每个格子可以是0~k，给出各行的和和各列的和，求格子数字唯一方案，或判断无解或不唯一。

题解：

最大流，每行一个点，每列一个点，起点到每行的点连流量等于这行的和的边，每列的点连流量等于这列的和的边到终点，每行的点连到每列的点流量为K的点。所有行的和不等于所有列的和或最大流不等于所有行的和则无解。有解的话再判有没有环，有环说明多解，可以dfs判环。

我这题卡了好久，判环的地方怒有问题，后来我看别人代码，只用从1~nr（行数）作为起始位置就能判完，也就是从行的节点开始，如果所有节点都开始一发的话会超时……我觉得再开点东西来记忆的话应该可以更快点，日后再说吧。

（我的网络流是n个点，下标1~n的ISAP+GAP+CUR，怕不怕）

代码：

  1 #include  2 #include  3 #include  4 #include  5 #include
  6 #include  7 #include  8 #includeset>
  9 using namespace std;
 10 #define ll __int64
 11 #define usint unsigned int
 12 #define RE  freopen("1002.in","r",stdin)
 13 #define WE  freopen("1002my.out","w",stdout)
 14 
 15 int ans;
 16 int r[444],co[444];
 17 int k,nr,nc;
 18 int sumr,sumc;
 19 const int maxn=1111;//点数
 20 const int maxm=444444;//边数
 21 const int inf=0x7fffffff;//MAXINT
 22 struct vnode {
 23     int v,next;
 24     int cap;
 25 };
 26 int cnt,head[maxn];
 27 int h[maxn],g[maxn],d[maxn];//g[i]为标号为i的结点个数，h[i]为i结点的标号，d[]当前弧优化，记录当前弧
 28 bool found;
 29 int n,m,st,ed;//n个点m条边
 30 int augc,flow;//augc为增广路容量，flow为最大流
 31 vnode e[maxm];
 32 
 33 void add(int x,int y,int z) {
 34     e[cnt].v=y;
 35     e[cnt].cap=z;
 36     e[cnt].next=head[x];
 37     head[x]=cnt;
 38     cnt++;
 39 //    if(cnt>=maxm|| x>=maxn||y>=maxn)
 40 //    {
 41 //        //cout 42 //        getchar();
 43 //    }
 44     e[cnt].v=x;
 45     e[cnt].cap=0;
 46     e[cnt].next=head[y];
 47     head[y]=cnt;
 48     cnt++;
 49 
 50 }
 51 
 52 
 53 bool walked[maxn];
 54 bool dfs(int x,int preE) {
 55     //cout
 56     for (int i=head[x]; i!=-1; i=e[i].next)//寻找容许边
 57     {
 58         if(i==(preE^1))continue;
 59         if (e[i].cap>0) { //如果残留容量大于0，如果不是直接回头
 60             if(walked[e[i].v])return true;
 61             walked[e[i].v]=true;
 62             if(dfs(e[i].v,i)) return true;
 63             walked[e[i].v]=false;
 64         }
 65     }
 66     //printf("(%d)out ",x);
 67     //getchar();
 68     return false;
 69 }
 70 
 71 void aug(const int &m) {
 72     int i,mini,minh=n-1;
 73     int augco=augc;
 74     if (m==ed) { //如果当前结点为汇点
 75         found=true;
 76         flow+=augc;    //增加流量
 77         return;
 78     }
 79     for (i=d[m]; i!=-1; i=e[i].next) { //寻找容许边
 80         //printf("m=%d,i=%d,e[i].v=%d,e[i].cap=%d,e[i].next=%d\n",m,i,e[i].v,e[i].cap,e[i].next);
 81         //getchar();
 82         if (e[i].cap && h[e[i].v]+1==h[m]) { //如果残留容量大于0，如果是容许边
 83             if (e[i].cap //如果容许边流量小于当前增广路流量 则更新增广路流量
 84             d[m]=i;    //把i定为当前弧
 85             aug(e[i].v);    //递归
 86             if (h[st]>=n) return; //GAP 如果源点距离标号大于n 则停止算法
 87             if (found) break;    //如果找到汇点 则退出寻找
 88             augc=augco;//没找到就还原当前的流
 89         }
 90     }
 91     if (!found) {      //重标号
 92         for (i=head[m]; i!=-1; i=e[i].next) //找那个标号，这里不能用d[m]开始，不然会蛋疼
 93             if (e[i].cap && h[e[i].v]minh) {
 94                 minh=h[e[i].v];
 95                 mini=i;
 96             }
 97         g[h[m]]--;                                 //GAP 距离为
 98         if (!g[h[m]]) h[st]=n;                 //GAP
 99         h[m]=minh+1;
100         d[m]=mini;
101         g[h[m]]++;                                 //GAP
102     } else {
103         //修改残量
104         e[i].cap-=augc;
105         e[i^1].cap+=augc;
106     }
107 }
108 
109 void farm() {
110     int i,j,x,y,z;
111     memset(head,-1,sizeof(head));
112     cnt=0;
113     n=nc+nr+2;
114     st=n-1;
115     ed=n;
116     for(i=nc; i>=1; i--)
117         add(st,i,co[i-1]);
118     for(i=nr; i>=1; i--)
119         add(nc+i,ed,r[i-1]);
120     for(i=nc; i>=1; i--)
121         for(j=nr; j>=1; j--)
122             add(i,nc+j,k);
123     //printf("cnt=%d\n",cnt);
124     memset(h,0,sizeof(h));
125     memset(g,0,sizeof(g));
126     g[0]=n;
127     flow=0;
128     //printf("st=%d,head[st]=%d\n",st,head[st]);
129     for(i=1; i)
130         d[i]=head[i];//当前弧初始化
131     while(h[st]n) {
132         augc=inf;//初始化增广路容量为正无穷大
133         found=false;
134         aug(st);//从源点开始找
135     }
136     if(flow!=sumr) {ans=0;return;}
137     //printf("%d\n",flow);
138     memset(walked,false,sizeof(walked));
139     for(i=1;i///Why is nr?
140     {
141         //printf("start dfs(%d)\n",i);
142         if(dfs(i,-1)) {ans=2;return;}
143     }
144     ans=1;
145     //printf("%d\n",flow);
146 }
147 
148 int main() {
149     //RE;
150     //WE;
151     int i,j;
152     while(scanf("%d%d%d",&nr,&nc,&k)!=EOF) {
153         sumr=0;sumc=0;
154         for(i=0; i)
155         {
156             scanf("%d",&r[i]);
157             sumr+=r[i];
158         }
159         for(i=0; i)
160         {
161             scanf("%d",&co[i]);
162             sumc+=co[i];
163         }
164         ans=0;
165         if(sumr==sumc)farm();
166         if(ans==0) printf("Impossible\n");
167         else if(ans!=1) {
168             printf("Not Unique\n");
169 //            for(i=1; i170 //                for(j=head[nc+i]; j!=-1; j=e[j].next)
171 //                {
172 //                    if(e[j].v==ed)continue;
173 //                    printf("%d ",e[j].cap);
174 //                }
175 //                puts("");
176 //            }
177         } else {
178             printf("Unique\n");
179             for(i=1; i) {
180                 for(j=head[nc+i]; j!=-1; j=e[j].next) {
181                     if(e[j].v==ed)continue;
182                     printf("%d",e[j].cap);
183                     int thenext=e[j].next;
184                     while(thenext!=-1&&e[thenext].v==ed)thenext=e[thenext].next;
185                     if(thenext!=-1)putchar(‘ ‘);
186                 }
187                 puts("");
188             }
189         }
190     }
191     //cout
192     return 0;
193 }

View Code

hdu4888 Redraw Beautiful Drawings 最大流+判环,搜素材,soscw.com

hdu4888 Redraw Beautiful Drawings 最大流+判环

标签：des style blog http color java os io

原文地址：http://www.cnblogs.com/yuiffy/p/3891639.html

上一篇：乐字节Java反射之三：方法、数组、类加载器和类的生命周期

下一篇：Web开发者不可不知的15条编码原则

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：hdu4888 Redraw Beautiful Drawings 最大流+判环
文章链接：http://soscw.com/essay/32099.html

亲，登录后才可以留言！

hdu4888 Redraw Beautiful Drawings 最大流+判环

Redraw Beautiful Drawings

评论

热门文章

推荐文章

最新文章

置顶文章