加入一个源点与汇点，建图例如以下：
1. 源点 -> 每一行相应的点，流量限制为该行的和
2. 每一行相应的点 -> 每一列相应的点，流量限制为 K
3. 每一列相应的点 -> 汇点，流量限制为该列的和
求一遍最大流，若最大流与矩阵之和相等，说明有解，，否则无解。推断唯一解，是推断残量网络中是否存在一个长度大于2的环。若存在说明有多解，否则有唯一解，解就是每条边行i->列j的流量。#include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) #define C 240 #define S 20 using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 810; const int maxm = 160000+810; struct node { int u,v,w,next; } edge[maxm << 1]; int cnt,head[maxn]; int n,m,k,s,t; int nn[410],mm[410]; int maxflow; int vis[maxn]; int dis[maxn]; void init() { cnt = 0; memset(head,-1,sizeof(head)); } void add(int u, int v, int f) { edge[cnt] = (struct node){u,v,f,head[u]}; head[u] = cnt++; edge[cnt] = (struct node){v,u,0,head[v]}; head[v] = cnt++; } bool bfs() { queue<int>que; while(!que.empty()) que.pop(); memset(dis,-1,sizeof(dis)); dis[s] = 0; que.push(s); while(!que.empty()) { int u = que.front(); que.pop(); for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(dis[v] == -1 && edge[i].w) { dis[v] = dis[u]+1; que.push(v); } } } if(dis[t] == -1) return false; return true; } int dfs(int u, int delta) { if(u == t || delta == 0) return delta; int dd; int ret = 0; for(int i = head[u]; i != -1 && delta; i = edge[i].next) { if(dis[edge[i].v] == dis[u]+1 && (dd = dfs(edge[i].v,min(delta,edge[i].w)))) { edge[i].w -= dd; edge[i^1].w += dd; delta -= dd; ret += dd; if(delta == 0) return ret; } } dis[u] = -1; return ret; } int Dinic() { int ret = 0; while(bfs()) { ret += dfs(s,INF); } return ret; } int dfs_1(int u,int fa) { for(int i=head[u]; i!=-1; i=edge[i].next) { if(i==(fa^1)) continue; if(edge[i].w) { if(vis[edge[i].v]) return 1; vis[edge[i].v]=1; if(dfs_1(edge[i].v,i)) return 1; vis[edge[i].v]=0; } } return 0; } void putmat() { int f[410][410]; printf("Unique\n"); for(int u = 1; u <= n; u++) { for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(v > n && v <= n+m) f[u][v-n] = k - edge[i].w; } } for(int i = 1; i <= n; i++) { for(int j = 1; j < m; j++) printf("%d ",f[i][j]); printf("%d\n",f[i][m]); } } int main() { while(~scanf("%d %d %d",&n,&m,&k)) { init(); s = 0; t = n+m+1; int sum1 = 0; int sum2 = 0; for(int i = 1; i <= n; i++) { scanf("%d",&nn[i]); add(s,i,nn[i]); sum1 += nn[i]; for(int j = 1; j <= m; j++) add(i,j+n,k); } for(int i = 1; i <= m; i++) { scanf("%d",&mm[i]); add(i+n,t,mm[i]); sum2 += mm[i]; } if(sum1 != sum2) { printf("Impossible\n"); } else { maxflow = Dinic(); if(maxflow != sum1) { printf("Impossible\n"); } else { int flag = 0; memset(vis,0,sizeof(vis)); for(int i = 1; i <= n; i++) { if(dfs_1(i,-1)) { flag = 1; break; } } if(flag == 1) printf("Not Unique\n"); else putmat(); } } } return 0; }