题目：
http://acm.hdu.edu.cn/showproblem.php?pid=4888
题意：
给一个n*m的矩阵的n行之和和m列之和以及限制k，使用0-k的数字填充矩阵使得其行与列之和为给定值
如果不行则输出Impossible
如果有多解则输出Not Unique
如果有一解则输出Unique，并输出构造的矩阵
方法：
最大流，判最大流有多解
1、建图：
每一行一个点，每一列一个点
源点与第i个行点连边，权值为第i行之和
第j个列点与汇点连边，权值为第j行之和
第i个行点与第j个列点连边，权值为k
2、跑最大流
3、如果源点与n个行点都流满且m个列点与汇点都流满，则有解，否则无解
4、判最大流有多解：
如果有多解，则某两点流量可以为(f1,f2)，(f1-f,f2+f)，所以可以根据这个结论判最大流是否有多解：
在残余网络中，如果存在大小大于2的环，则可以出现上述情况，即：有多解
1 bool dfsc(int u, int fa) 2 { 3 vis[u] = 1; 4 for (int i = head[u]; ~i; i = edge[i].next) 5 { 6 int v = edge[i].v; 7 if (v == fa || edge[i].flow == edge[i].cap) continue; 8 if (vis[v] || dfsc(v, u)) return 1; 9 } 10 vis[u] = 0; 11 return 0; 12 } 13 bool check() 14 { 15 memset(vis, 0, sizeof(vis)); 16 for (int i = 2; i < N + 2; i++) 17 { 18 if (!vis[i]) 19 { 20 vis[i] = 1; 21 if (dfsc(i, i)) return 0; 22 vis[i] = 0; 23 } 24 } 25 return 1; 26 }
5、构造矩阵：
第i个行点与第j个列点的流量即为(i,j)的值
代码：
1 // #pragma comment(linker, "/STACK:102400000,102400000") 2 #include <cstdio> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <set> 8 #include <list> 9 #include <map> 10 #include <iterator> 11 #include <cstdlib> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <algorithm> 16 #include <functional> 17 using namespace std; 18 typedef long long LL; 19 #define ROUND(x) round(x) 20 #define FLOOR(x) floor(x) 21 #define CEIL(x) ceil(x) 22 // const int maxn = 0; 23 // const int maxm = 0; 24 // const int inf = 0x3f3f3f3f; 25 const LL inf64 = 0x3f3f3f3f3f3f3f3fLL; 26 const double INF = 1e30; 27 const double eps = 1e-6; 28 const int P[4] = {0, 0, -1, 1}; 29 const int Q[4] = {1, -1, 0, 0}; 30 const int PP[8] = { -1, -1, -1, 0, 0, 1, 1, 1}; 31 const int QQ[8] = { -1, 0, 1, -1, 1, -1, 0, 1}; 32 33 /** 34 *最大流最小割：加各种优化的Dinic算法($O(V^2E)$) 35 *输入：图(链式前向星),n(顶点个数,包含源汇),st(源),ed(汇) 36 *输出：Dinic(NdFlow)(最大流),MinCut()(最小割)(需先求最大流) 37 *打印路径方法：按反向边(i&1)的flow 找，或者按边的flow找 38 */ 39 const int maxn = 810; 40 const int maxm = 400010; 41 const int inf = 0x3f3f3f3f; 42 struct Edge 43 { 44 int u, v; 45 int cap, flow; 46 int next; 47 } edge[maxm]; 48 int head[maxn], en; //需初始化 49 int n, m, d[maxn], cur[maxn]; 50 int st, ed; 51 bool vis[maxn]; 52 void addse(int u, int v, int cap, int flow) 53 { 54 edge[en].u = u; 55 edge[en].v = v; 56 edge[en].cap = cap; 57 edge[en].flow = flow; 58 edge[en].next = head[u]; 59 head[u] = en++; 60 cur[u] = head[u]; 61 } 62 void adde(int u, int v, int cap) 63 { 64 addse(u, v, cap, 0); 65 addse(v, u, 0, 0); //注意加反向0边 66 } 67 bool BFS() 68 { 69 queue<int> Q; 70 memset(vis, 0, sizeof(vis)); 71 Q.push(st); 72 d[st] = 0; 73 vis[st] = 1; 74 while (!Q.empty()) 75 { 76 int u = Q.front(); 77 Q.pop(); 78 for (int i = head[u]; i != -1; i = edge[i].next) 79 { 80 int v = edge[i].v; 81 int w = edge[i].cap - edge[i].flow; 82 if (w > 0 && !vis[v]) 83 { 84 vis[v] = 1; 85 Q.push(v); 86 d[v] = d[u] + 1; 87 if (v == ed) return 1; 88 } 89 } 90 } 91 return false; 92 } 93 int Aug(int u, int a) 94 { 95 if (u == ed) return a; 96 int aug = 0, delta; 97 for (int &i = cur[u]; i != -1; i = edge[i].next) 98 { 99 int v = edge[i].v; 100 int w = edge[i].cap - edge[i].flow; 101 if (w > 0 && d[v] == d[u] + 1) 102 { 103 delta = Aug(v, min(a, w)); 104 if (delta) 105 { 106 edge[i].flow += delta; 107 edge[i ^ 1].flow -= delta; 108 aug += delta; 109 if (!(a -= delta)) break; 110 } 111 } 112 } 113 if (!aug) d[u] = -1; 114 return aug; 115 } 116 int Dinic(int NdFlow) 117 { 118 int flow = 0; 119 while (BFS()) 120 { 121 memcpy(cur, head, sizeof(int) * (n + 1)); 122 flow += Aug(st, inf); 123 /*如果超过指定流量就return 掉*/ 124 if (NdFlow == inf) continue; 125 if (flow > NdFlow) break; 126 } 127 return flow; 128 } 129 /*残余网络*/ 130 void Reduce() 131 { 132 for (int i = 0; i < en; i++) edge[i].cap -= edge[i].flow; 133 } 134 /*清空流量*/ 135 void ClearFlow() 136 { 137 for (int i = 0; i < en; i++) edge[i].flow = 0; 138 } 139 /*求最小割*/ 140 vector<int> MinCut() 141 { 142 BFS(); 143 vector<int> ans; 144 for (int u = 0; u < n; u++) 145 { 146 if (!vis[u]) continue; 147 for (int i = head[u]; i != -1; i = edge[i].next) 148 { 149 if (i & 1) continue; /*忽略反向边*/ 150 int v = edge[i].v; 151 int w = edge[i].cap; 152 if (!vis[v] && w > 0) ans.push_back(i); 153 } 154 } 155 return ans; 156 } 157 158 int N, M, K; 159 int a[maxn], b[maxn]; 160 int mtx[410][410]; 161 void init() 162 { 163 memset(head, -1, sizeof(head)); 164 en = 0; 165 } 166 void input() 167 { 168 for (int i = 0; i < N; i++) 169 scanf("%d", &a[i]); 170 for (int i = 0; i < M; i++) 171 scanf("%d", &b[i]); 172 } 173 void debug() 174 { 175 // 176 } 177 void build() 178 { 179 st = 0, ed = 1; 180 n = N + M + 2; 181 for (int i = 0; i < N; i++) 182 { 183 adde(st, i + 2, a[i]); 184 } 185 for (int i = 0; i < M; i++) 186 { 187 adde(i + N + 2, ed, b[i]); 188 } 189 for (int i = 0; i < N; i++) 190 { 191 for (int j = 0; j < M; j++) 192 { 193 adde(i + 2, j + N + 2, K); 194 } 195 } 196 } 197 bool dfsc(int u, int fa) 198 { 199 vis[u] = 1; 200 for (int i = head[u]; ~i; i = edge[i].next) 201 { 202 int v = edge[i].v; 203 if (v == fa || edge[i].flow == edge[i].cap) continue; 204 if (vis[v] || dfsc(v, u)) return 1; 205 } 206 vis[u] = 0; 207 return 0; 208 } 209 bool check() 210 { 211 memset(vis, 0, sizeof(vis)); 212 for (int i = 2; i < N + 2; i++) 213 { 214 if (!vis[i]) 215 { 216 vis[i] = 1; 217 if (dfsc(i, i)) return 0; 218 vis[i] = 0; 219 } 220 } 221 return 1; 222 } 223 void solve() 224 { 225 build(); 226 Dinic(inf); 227 // cout << "flow: " << Dinic(inf) << endl; 228 int flag = 1; 229 for (int i = head[st]; ~i; i = edge[i].next) 230 { 231 if (i & 1) continue; 232 if (edge[i].cap > edge[i].flow) 233 { 234 flag = 0; 235 break; 236 } 237 } 238 for (int i = head[ed]; ~i; i = edge[i].next) 239 { 240 if (i & 0) continue; 241 if (-edge[i].flow < edge[i ^ 1].flow) 242 { 243 flag = 0; 244 break; 245 } 246 } 247 if (!flag) 248 { 249 puts("Impossible"); 250 return; 251 } 252 if (!check()) 253 { 254 puts("Not Unique"); 255 return; 256 } 257 for (int u = 0; u < N; u++) 258 { 259 for (int i = head[u + 2]; ~i; i = edge[i].next) 260 { 261 if (i & 1) continue; 262 int v = edge[i].v - N - 2; 263 mtx[u][v] = edge[i].flow; 264 } 265 } 266 puts("Unique"); 267 for (int i = 0; i < N; i++) 268 { 269 for (int j = 0; j < M; j++) 270 { 271 if (j < M - 1) printf("%d ", mtx[i][j]); 272 else printf("%d\n", mtx[i][j]); 273 } 274 } 275 } 276 void output() 277 { 278 // 279 } 280 int main() 281 { 282 // int size = 256 << 20; // 256MB 283 // char *p = (char *)malloc(size) + size; 284 // __asm__("movl %0, %%esp\n" :: "r"(p)); 285 286 // std::ios_base::sync_with_stdio(false); 287 #ifndef ONLINE_JUDGE 288 freopen("in.cpp", "r", stdin); 289 #endif 290 291 while (~scanf("%d%d%d", &N, &M, &K)) 292 { 293 init(); 294 input(); 295 solve(); 296 output(); 297 } 298 return 0; 299 }
HDU 4888 Redraw Beautiful Drawings (2014-多校3-1002，最大流，判最大流有多解),布布扣,bubuko.com
HDU 4888 Redraw Beautiful Drawings (2014-多校3-1002，最大流，判最大流有多解)