题意：给定n*m个格子，每个格子能填0-k 的整数。然后给出每列之和和每行之和，问有没有解，有的话是不是唯一解，是唯一解输出方案。
思路：网络流，一共 n+m+2个点 源点 到行连流量为 所给的 当前行之和。 每行 连到每一列 一条流量为 k的边，每列到汇点连 列和。如果流量等于总和则有解，反之无解（如果列总和不等于行总和也无解）。 判断方案是否唯一 找残留网络是否存在长度大于2的环即可，有环说明不唯一。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include <iostream> #include<climits> using namespace std; const int N = 1000; const int M = 1000000; int n; int ecnt, head[N], nx[M], to[M], va[M], cur_edge[N]; int source, target, flow, pre[N], lev[N], qu[N], sign; void addedge(int u, int v, int w) { to[ecnt] = v; nx[ecnt] = head[u]; va[ecnt] = w; head[u] = ecnt++; } bool bfs(int s, int t) { std::fill(lev, lev + n, -1); sign = t; lev[t] = 0; int st = 0, ed = 0; qu[ed++] = t; while (st != ed && lev[s] == -1) { int u = qu[st++]; for (int i = head[u]; i != -1; i = nx[i]) { if (va[i ^ 1] > 0 && lev[to[i]] == -1) { lev[to[i]] = lev[u] + 1; qu[ed++] = to[i]; } } } return lev[s] != -1; } void push() { int delta = INT_MAX, u, p; for (u = target; u != source; u = to[p ^ 1]) { p = pre[u]; delta = std::min(delta, va[p]); } for (u = target; u != source; u = to[p ^ 1]) { p = pre[u]; va[p] -= delta; if (!va[p]) {//注意double时要改 sign = to[p ^ 1]; } va[p ^ 1] += delta; } flow += delta; } void dfs(int u) { if (u == target) push(); else { for (int i = cur_edge[u]; i != -1; i = nx[i]) { if (va[i] > 0 && lev[u] == lev[to[i]] + 1) { pre[to[i]] = i; dfs(to[i]); if (lev[sign] > lev[u]) { return; } sign = target; } } lev[u] = -1; } } void dinic(int s, int t, int node_cnt) { source = s; target = t; n = node_cnt; //construct graph flow = 0; while (bfs(source, target)) { for (int i = 0; i < n; ++i) { cur_edge[i] = head[i]; } dfs(source); } } int nc, kc, mc, sum1, sum2; int r[410], c[410]; void init() { sum1 = sum2 = 0; for (int i = 0; i < nc; ++i) { scanf("%d", &r[i]); sum1 += r[i]; } for (int i = 0; i < mc; ++i) { scanf("%d", &c[i]); sum2 += c[i]; } } int flag = 0; bool bo[1000]; bool bb[1000]; int cas[350000]; int ri = 0; void gao(int now, int fa) {//找环 if(flag)return; //printf("->%d ",now); bo[now] = true; for (int i = head[now]; i != -1; i = nx[i]) { int u = to[i]; if (u == fa) continue; if (va[i] == 0) continue; // printf(" {%d %d} ",now,u); if (bb[u]) { // puts("fuck"); flag = 1; return; } if (cas[i] == ri) continue; cas[i] = ri; //if(bo[u])continue; bb[u] = true; gao(u, now); bb[u] = false; } } void solve() { if (sum1 != sum2) { puts("Impossible"); return; } std::fill(head, head + mc + nc + 5, -1); ecnt = 0; int s, t; s = nc + mc; t = s + 1; // printf("st:%d %d ",s,t); for (int i = 0; i < nc; ++i) { for (int j = 0; j < mc; ++j) { // printf("[%d %d] ",i,j+nc); addedge(i, j + nc, kc); addedge(j + nc, i, 0); } } for (int i = 0; i < nc; ++i) { // printf("[%d %d] ",s,i); addedge(s, i, r[i]); addedge(i, s, 0); } for (int i = 0; i < mc; ++i) { // printf("[%d %d] ",i+nc,t); addedge(i + nc, t, c[i]); addedge(t, i + nc, 0); } dinic(s, t, t + 2); // printf("flow:%d ",flow); if (flow == sum1) { memset(bo, 0, sizeof(bo)); memset(bb, 0, sizeof(bb)); flag = 0; for (int i = 0; i <= t; ++i) { if(flag)break; bb[i] = true; gao(i, -1); bb[i] = false; } if (flag) puts("Not Unique"); else { puts("Unique"); for (int i = 0; i < nc; ++i) { for (int j = 0; j < mc; ++j) { int now = i * mc + j; printf("%d", va[now << 1 | 1]); if (j == mc - 1) puts(""); else printf(" "); } } } } else puts("Impossible"); } int main() { memset(cas, 0, sizeof(cas)); while (scanf("%d%d%d", &nc, &mc, &kc) != EOF) { ++ri; init(); solve(); } return 0; }