题意就是
给一个50 * 50的矩阵
然后给出每行每列元素的和
和一个初始矩阵
矩阵中有些是未知，有些是已知
然后我们求目标矩阵就是把能确定的元素的值求出来，实在不能确定的就置为-1
所有矩阵元素的值在0-100之间
看到范围很小。
第一反应是求一个最大流
先把已经给出的元素都从每行每列的和中减掉。
然后左边为行结点，右边为列结点
然后源点向行结点连边
列结点向汇点连边
行和列中如果对应的元素未知就连一下，流向上限是100
然后这样我们就得到了一个可行解
但是可能有多解怎么办
对于一个可能多解的元素
如果我们将这个元素的值固定住。
然后建立一个超级源点与该行结点连边。
该列结点与超级汇点连边。
流量都是1,
跑一遍看看有没有增广路。
如果有，显然这个位置的值是可以改变的，就是多解，然后我们把这个位置的元素值-1,因为我们刚才增广了，其他有元素的值增加了1，所以
为了保持流量的平衡，这个位置的元素要减1
但是这样还不行。
我们想想。
如果该位置的值现在是0怎么办。
他没法减掉1。
所以我们就要想想残余网络了。
既然他没法减掉1，就让他想办法+1，让别的元素-1去
那么我们可以用一个超级源点连接列结点。
行结点连接超级汇点
跑最大流，看有没有增广路。
也就是看他的残余网络能不能减掉1.即它自身+1
如果有增广路，跟之前一样，更新一下边
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#define MAXN 106
#define MAXM 211111
#define INF 1111111111
using namespace std;
struct EDGE
{int v, next;int w;
}edge[MAXM];
int head[MAXN], e;
void init()
{memset(head, -1, sizeof(head));e = 0;
}
void add(int u, int v, int w)
{edge[e].v = v;edge[e].w = w;edge[e].next = head[u];head[u] = e++;edge[e].v = u;edge[e].w = 0;edge[e].next = head[v];head[v] = e++;
}
int n;
int h[MAXN];
int gap[MAXN];
int src, des;
int tt[111][111];
int dfs(int pos, int cost)
{if(pos == des) return cost;int j, minh = n - 1;int lv = cost, d;for(j = head[pos]; j != -1; j = edge[j].next){int v = edge[j].v;int w = edge[j].w;if(w > 0){if(h[v] + 1 == h[pos]){if(lv < edge[j].w) d = lv;else d = edge[j].w;d = dfs(v, d);edge[j].w -= d;edge[j ^ 1].w += d;lv -= d;if(h[src] >= n) return cost - lv;if(lv == 0) break;}if(h[v] < minh) minh = h[v];}}if(lv == cost){--gap[h[pos]];if(gap[h[pos]] == 0) h[src] = n;h[pos] = minh + 1;++gap[h[pos]];}return cost - lv;
}
int sap()
{int ret = 0;memset(gap, 0, sizeof(gap));memset(h, 0, sizeof(h));gap[0] = n;while(h[src] < n) ret += dfs(src, INF);return ret;
}
int nt, m;
int col[55], row[55];
int val[55][55], id[55][55];
int ans[55][55];
int vis[55][55];int main()
{//freopen("C:/C.in", "r", stdin);//freopen("C:/C2.out", "w", stdout);while(scanf("%d%d", &nt, &m) != EOF){if(!nt && !m) break;for(int i = 1; i <= nt; i++)for(int j = 1; j <= m; j++)scanf("%d", &val[i][j]);for(int i = 1; i <= nt; i++) scanf("%d", &row[i]);for(int i = 1; i <= m; i++) scanf("%d", &col[i]);memset(ans, -1, sizeof(ans));for(int i = 1; i <= nt; i++)for(int j = 1; j <= m; j++){if(val[i][j] != -1){row[i] -= val[i][j];col[j] -= val[i][j];ans[i][j] = val[i][j];}}init();src = nt + m + 1;des = nt + m + 2;n = des;int S = nt + m + 3;int T = nt + m + 4;for(int i = 1; i <= nt; i++)for(int j = 1; j <= m; j++){if(ans[i][j] == -1){id[i][j] = e;add(i, j + nt, 100);}}for(int i = 1; i <= nt; i++){add(src, i, row[i]);}for(int j = 1; j <= m; j++){add(j + nt, des, col[j]);}sap();n = T;memset(vis, 0, sizeof(vis));for(int i = 1; i <= nt; i++)for(int j = 1; j <= m; j++)if(ans[i][j] != -1) vis[i][j] = 2;src = S;des = T;for(int i = 1; i <= nt; i++){for(int j = 1; j <= m; j++){if(vis[i][j] == 2) continue;int te = id[i][j];int tmp = edge[te ^ 1].w;edge[te].w = edge[te ^ 1].w = 0;int flag = 1;int le = e;add(src, i, 1);int me = e;add(j + nt, des, 1);if( tmp && sap()) flag = 0, tmp--;edge[le].w = edge[le ^ 1].w = 0;edge[me].w = edge[me ^ 1].w = 0;le = e;add(src, j + nt, 1);me = e;add(i, des, 1);if(flag && 100 - tmp > 0&& sap()) flag = 0, tmp++;edge[le].w = edge[le ^ 1].w = 0;edge[me].w = edge[me ^ 1].w = 0;edge[te ^ 1].w = tmp;edge[te].w = 100 - tmp;vis[i][j] = flag;}}for(int i = 1; i <= nt; i++)for(int j = 1; j <= m; j++){if(vis[i][j] == 2){if(ans[i][j] != -1) printf("%d", ans[i][j]);}else{if(vis[i][j]) printf("%d", edge[id[i][j] ^ 1].w);else printf("-1");}if(j < m) printf(" ");else printf("\n");}}return 0;
}