题意：给定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 = ;
const int M = ;
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, -);
sign = t;
lev[t] = ;
int st = , ed = ;
qu[ed++] = t;
while (st != ed && lev[s] == -) {
int u = qu[st++];
for (int i = head[u]; i != -; i = nx[i]) {
if (va[i ^ ] > && lev[to[i]] == -) {
lev[to[i]] = lev[u] + ;
qu[ed++] = to[i];
}
}
}
return lev[s] != -;
}
void push() {
int delta = INT_MAX, u, p;
for (u = target; u != source; u = to[p ^ ]) {
p = pre[u];
delta = std::min(delta, va[p]);
}
for (u = target; u != source; u = to[p ^ ]) {
p = pre[u];
va[p] -= delta;
if (!va[p]) {//注意double时要改
sign = to[p ^ ];
}
va[p ^ ] += delta;
}
flow += delta;
}
void dfs(int u) {
if (u == target)
push();
else {
for (int i = cur_edge[u]; i != -; i = nx[i]) {
if (va[i] > && lev[u] == lev[to[i]] + ) {
pre[to[i]] = i;
dfs(to[i]);
if (lev[sign] > lev[u]) {
return;
}
sign = target;
}
}
lev[u] = -;
}
}
void dinic(int s, int t, int node_cnt) {
source = s;
target = t;
n = node_cnt; //construct graph flow = ;
while (bfs(source, target)) {
for (int i = ; i < n; ++i) {
cur_edge[i] = head[i];
}
dfs(source);
} }
int nc, kc, mc, sum1, sum2;
int r[], c[];
void init() {
sum1 = sum2 = ;
for (int i = ; i < nc; ++i) {
scanf("%d", &r[i]);
sum1 += r[i];
}
for (int i = ; i < mc; ++i) {
scanf("%d", &c[i]);
sum2 += c[i];
}
}
int flag = ;
bool bo[];
bool bb[];
int cas[];
int ri = ;
void gao(int now, int fa) {//找环
if(flag)return;
//printf("->%d ",now);
bo[now] = true;
for (int i = head[now]; i != -; i = nx[i]) {
int u = to[i];
if (u == fa)
continue;
if (va[i] == )
continue; // printf(" {%d %d}\n",now,u);
if (bb[u]) {
// puts("fuck");
flag = ;
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 + , -);
ecnt = ;
int s, t;
s = nc + mc;
t = s + ;
// printf("st:%d %d\n",s,t);
for (int i = ; i < nc; ++i) {
for (int j = ; j < mc; ++j) { // printf("[%d %d]\n",i,j+nc);
addedge(i, j + nc, kc);
addedge(j + nc, i, );
}
}
for (int i = ; i < nc; ++i) {
// printf("[%d %d]\n",s,i);
addedge(s, i, r[i]);
addedge(i, s, );
}
for (int i = ; i < mc; ++i) { // printf("[%d %d]\n",i+nc,t);
addedge(i + nc, t, c[i]);
addedge(t, i + nc, );
}
dinic(s, t, t + );
// printf("flow:%d\n",flow);
if (flow == sum1) { memset(bo, , sizeof(bo));
memset(bb, , sizeof(bb));
flag = ;
for (int i = ; i <= t; ++i) {
if(flag)break;
bb[i] = true;
gao(i, -);
bb[i] = false;
}
if (flag)
puts("Not Unique");
else {
puts("Unique");
for (int i = ; i < nc; ++i) {
for (int j = ; j < mc; ++j) {
int now = i * mc + j;
printf("%d", va[now << | ]);
if (j == mc - )
puts("");
else
printf(" ");
}
}
}
} else
puts("Impossible");
}
int main() {
memset(cas, , sizeof(cas));
while (scanf("%d%d%d", &nc, &mc, &kc) != EOF) {
++ri;
init();
solve();
}
return ;
}