首页 > 代码库 > HDU 4888 Redraw Beautiful Drawings（最大流+判最大流网络是否唯一）
HDU 4888 Redraw Beautiful Drawings（最大流+判最大流网络是否唯一）
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.
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.
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).
题目大意：有一个矩阵，矩阵的数为0~K。给出矩阵每一行每一列的和。若不存在符合条件的矩阵，输出Impossible。若存在但矩阵不唯一，输出Not Unique。否则输出Unique并输出这个矩阵。
思路：网络最大流，另外开一个源点S和汇点T，源点到每行连一条边，容量为每一行的和。每一列到汇点连一条边，容量为每一列的和。每一行到每一列连一条边，容量为K。判断每行的总和和每列的总和是否相等，不等则输出Impossible，若相等，令这个值为sum。若sum不等于最大流，输出Impossible。否则，判断网络流是否唯一，不唯一输出Not Unique，存在则输出Unique，输出矩阵，矩阵mat[i][j]的值对应第 i 行到第 j 列的边的流量。
至于判断网络流是否唯一，可以采取在残量网络中找环的办法（环的大小必须大于2），若存在环，那么环上的边全部加一，得到一个新的残量网络，则最大流网络不唯一。那么问题转换为如何找环，由于环必然有至少一个点在列点上，而残量网络中，汇点对所有的列点都有边，那么可以从汇点开始DFS找环。
DFS判是否存在环可以借鉴tarjan求双连通分量的算法，具体可以看代码（这一步的复杂度为O(V + E)即O(n^2)，虽然更粗暴的方法也可以过，但是跑得没那么快。）。
代码（218MS）：
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <queue> 6 #include <numeric> 7 using namespace std; 8 typedef long long LL; 9 10 const int MAXN = 410; 11 const int MAXV = MAXN << 1; 12 const int MAXE = 2 * MAXN * MAXN; 13 const int INF = 0x3f3f3f3f; 14 15 struct ISAP { 16 int head[MAXV], cur[MAXV], gap[MAXV], dis[MAXV], pre[MAXV]; 17 int to[MAXE], next[MAXE], flow[MAXE]; 18 int n, ecnt, st, ed; 19 20 void init(int n) { 21 this->n = n; 22 memset(head + 1, -1, n * sizeof(int)); 23 ecnt = 0; 24 } 25 26 void add_edge(int u, int v, int c) { 27 to[ecnt] = v; flow[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++; 28 to[ecnt] = u; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++; 29 } 30 31 void bfs() { 32 memset(dis + 1, 0x3f, n * sizeof(int)); 33 queue<int> que; que.push(ed); 34 dis[ed] = 0; 35 while(!que.empty()) { 36 int u = que.front(); que.pop(); 37 gap[dis[u]]++; 38 for(int p = head[u]; ~p; p = next[p]) { 39 int v = to[p]; 40 if(flow[p ^ 1] && dis[u] + 1 < dis[v]) { 41 dis[v] = dis[u] + 1; 42 que.push(v); 43 } 44 } 45 } 46 } 47 48 int max_flow(int ss, int tt) { 49 st = ss, ed = tt; 50 int ans = 0, minFlow = INF; 51 for(int i = 0; i <= n; ++i) { 52 cur[i] = head[i]; 53 gap[i] = 0; 54 } 55 bfs(); 56 int u = pre[st] = st; 57 while(dis[st] < n) { 58 bool flag = false; 59 for(int &p = cur[u]; ~p; p = next[p]) { 60 int v = to[p]; 61 if(flow[p] && dis[u] == dis[v] + 1) { 62 flag = true; 63 minFlow = min(minFlow, flow[p]); 64 pre[v] = u; 65 u = v; 66 if(u == ed) { 67 ans += minFlow; 68 while(u != st) { 69 u = pre[u]; 70 flow[cur[u]] -= minFlow; 71 flow[cur[u] ^ 1] += minFlow; 72 } 73 minFlow = INF; 74 } 75 break; 76 } 77 } 78 if(flag) continue; 79 int minDis = n - 1; 80 for(int p = head[u]; ~p; p = next[p]) { 81 int &v = to[p]; 82 if(flow[p] && dis[v] < minDis) { 83 minDis = dis[v]; 84 cur[u] = p; 85 } 86 } 87 if(--gap[dis[u]] == 0) break; 88 ++gap[dis[u] = minDis + 1]; 89 u = pre[u]; 90 } 91 return ans; 92 } 93 94 int stk[MAXV], top; 95 bool sccno[MAXV], vis[MAXV]; 96 97 bool dfs(int u, int f, bool flag) { 98 vis[u] = true; 99 stk[top++] = u;100 for(int p = head[u]; ~p; p = next[p]) if(flow[p]) {101 int v = to[p];102 if(v == f) continue;103 if(!vis[v]) {104 if(dfs(v, u, flow[p ^ 1])) return true;105 } else if(!sccno[v]) return true;106 }107 if(!flag) {108 while(true) {109 int x = stk[--top];110 sccno[x] = true;111 if(x == u) break;112 }113 }114 return false;115 }116 117 bool acycle() {118 memset(sccno + 1, 0, n * sizeof(bool));119 memset(vis + 1, 0, n * sizeof(bool));120 top = 0;121 return dfs(ed, 0, 0);122 }123 } G;124 125 int row[MAXN], col[MAXN];126 int mat[MAXN][MAXN];127 int n, m, k, ss, tt;128 129 void solve() {130 int sumr = accumulate(row + 1, row + n + 1, 0);131 int sumc = accumulate(col + 1, col + m + 1, 0);132 if(sumr != sumc) {133 puts("Impossible");134 return ;135 }136 int res = G.max_flow(ss, tt);137 if(res != sumc) {138 puts("Impossible");139 return ;140 }141 if(G.acycle()) {142 puts("Not Unique");143 } else {144 puts("Unique");145 for(int i = 1; i <= n; ++i) {146 for(int j = 1; j < m; ++j) printf("%d ", G.flow[mat[i][j]]);147 printf("%d\n", G.flow[mat[i][m]]);148 }149 }150 }151 152 int main() {153 while(scanf("%d%d%d", &n, &m, &k) != EOF) {154 for(int i = 1; i <= n; ++i) scanf("%d", &row[i]);155 for(int i = 1; i <= m; ++i) scanf("%d", &col[i]);156 ss = n + m + 1, tt = n + m + 2;157 G.init(tt);158 for(int i = 1; i <= n; ++i) G.add_edge(ss, i, row[i]);159 for(int i = 1; i <= m; ++i) G.add_edge(n + i, tt, col[i]);160 for(int i = 1; i <= n; ++i) {161 for(int j = 1; j <= m; ++j) {162 mat[i][j] = G.ecnt ^ 1;163 G.add_edge(i, n + j, k);164 }165 }166 solve();167 }168 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。