一个n*m的方格， 里面有<=k的数， 给出每一行所有数的和， 每一列所有数的和， 问你能否还原这个图， 如果能， 是否唯一， 如果唯一， 输出还原后的图。
首先对行列建边， 源点向行建边， 权值为这一行的和， 列向汇点建边， 权值为列和， 每一行向每一列建边， 权值为k， 因为上限是k。
然后跑一遍最大流， 如果最大流和所有行的和以及所有列的和相等， 那么可以还原。
判断是否唯一， 用判环的方式， 对图中每一个点dfs， 如果存在环， 说明原图不唯一。
原图每个格子的值等于k-这个格子的行与列之间的那条边的权值。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define lson l, m, rt<<1 7 #define mem(a) memset(a, 0, sizeof(a)) 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const double eps = 1e-8; 16 const int mod = 1e9+7; 17 const int inf = 1061109567; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 const int maxn = 1e6+5; 20 int q[maxn*2], head[maxn*2], dis[maxn/10], s, t, num, vis[1005], cnt, col[405], row[405], g[405][405]; 21 struct node 22 { 23 int to, nextt, c; 24 node(){} 25 node(int to, int nextt, int c):to(to), nextt(nextt), c(c){} 26 }e[maxn*2]; 27 void init() { 28 num = cnt = 0; 29 mem1(head); 30 mem(vis); 31 } 32 void add(int u, int v, int c) { 33 e[num] = node(v, head[u], c); head[u] = num++; 34 e[num] = node(u, head[v], 0); head[v] = num++; 35 } 36 int bfs() { 37 mem(dis); 38 dis[s] = 1; 39 int st = 0, ed = 0; 40 q[ed++] = s; 41 while(st<ed) { 42 int u = q[st++]; 43 for(int i = head[u]; ~i; i = e[i].nextt) { 44 int v = e[i].to; 45 if(!dis[v]&&e[i].c) { 46 dis[v] = dis[u]+1; 47 if(v == t) 48 return 1; 49 q[ed++] = v; 50 } 51 } 52 } 53 return 0; 54 } 55 int dfs(int u, int limit) { 56 if(u == t) { 57 return limit; 58 } 59 int cost = 0; 60 for(int i = head[u]; ~i; i = e[i].nextt) { 61 int v = e[i].to; 62 if(e[i].c&&dis[v] == dis[u]+1) { 63 int tmp = dfs(v, min(limit-cost, e[i].c)); 64 if(tmp>0) { 65 e[i].c -= tmp; 66 e[i^1].c += tmp; 67 cost += tmp; 68 if(cost == limit) 69 break; 70 } else { 71 dis[v] = -1; 72 } 73 } 74 } 75 return cost; 76 } 77 int dinic() { 78 int ans = 0; 79 while(bfs()) { 80 ans += dfs(s, inf); 81 } 82 return ans; 83 } 84 int dfs1(int u, int fa) { 85 if(vis[u]) 86 return 1; 87 vis[u] = 1; 88 for(int i = head[u]; ~i; i = e[i].nextt) { 89 int v = e[i].to; 90 if(v==fa||v==s||v==t) { 91 continue; 92 } 93 if(e[i].c) { 94 if(dfs1(v, u)) 95 return 1; 96 } 97 } 98 vis[u] = 0; 99 return 0; 100 } 101 int main() 102 { 103 int n, m, x, limit; 104 while(~scanf("%d%d%d", &n, &m, &limit)) { 105 init(); 106 int sum1 = 0, sum2 = 0; 107 s = 0, t = n+m+1; 108 for(int i = 1; i<=n; i++) { 109 scanf("%d", &x); 110 add(s, i, x); 111 sum2+=x; 112 for(int j = 1; j<=m; j++) { 113 add(i, j+n, limit); 114 } 115 } 116 for(int i = 1; i<=m; i++) { 117 scanf("%d", &x); 118 add(i+n, t, x); 119 sum1+=x; 120 } 121 int ans = dinic(), flag = 0; 122 if(ans != sum1 || sum2!=ans) { 123 puts("Impossible"); 124 continue; 125 } 126 for(int i = 1; i<=n; i++) { 127 if(dfs1(i, -1)) { 128 flag = 1; 129 break; 130 } 131 } 132 if(flag) { 133 puts("Not Unique"); 134 continue; 135 } 136 for(int u = 1; u<=n; u++) { 137 for(int i = head[u]; ~i; i = e[i].nextt) { 138 int v = e[i].to; 139 if(v>n&&v<=n+m) { 140 g[u][v-n] = limit-e[i].c; 141 } 142 } 143 } 144 puts("Unique"); 145 for(int i = 1; i<=n; i++) { 146 for(int j = 1; j<m; j++) { 147 printf("%d ", g[i][j]); 148 } 149 printf("%d ", g[i][m]); 150 } 151 } 152 return 0; 153 }