网络流。

$s$向每一个$r[i]$连边,容量为$r[i]$。

每一个$r[i]$向每一个$c[j]$连边,容量为$k$。

每一个$c[j]$向$t$连边容量为$c[j]$。

跑最大流,中间每一条边上的容量就是那一个格子所填的数字。

唯一性判定:如果残留网络上有环,那么不唯一。

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define ms(x,y) memset(x,y,sizeof(x))
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
#define loop(i,j,k) for (int i=j;i!=-1;i=k[i])
#define inone(x) scanf("%d",&x)
#define intwo(x,y) scanf("%d%d",&x,&y)
#define inthr(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define infou(x,y,z,p) scanf("%d%d%d%d",&x,&y,&z,&p)
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define mp(i,j) make_pair(i,j)
#define ft first
#define sd second
typedef long long LL;
typedef pair<int, int> pii;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + ;
const int N = 4e5 + ;
const double eps = 1e-; int n,m,k; const int maxn = + ;
struct Edge
{
int from, to, cap, flow;
Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){}
};
vector<Edge>edges;
vector<int>G[maxn],GG[maxn];
bool vis[maxn];
int d[maxn];
int cur[maxn],q[maxn];
int s, t,FF,sz; void init()
{
for (int i = ; i < maxn; i++) G[i].clear();
for (int i = ; i < maxn; i++) GG[i].clear(); edges.clear();
} void AddEdge(int from, int to, int cap)
{
edges.push_back(Edge(from, to, cap, ));
edges.push_back(Edge(to, from, , ));
int w = edges.size();
G[from].push_back(w - );
G[to].push_back(w - );
} bool BFS()
{
memset(vis, , sizeof(vis));
queue<int>Q;
Q.push(s);
d[s] = ;
vis[s] = ;
while (!Q.empty())
{
int x = Q.front();
Q.pop();
for (int i = ; i<G[x].size(); i++)
{
Edge e = edges[G[x][i]];
if (!vis[e.to] && e.cap>e.flow)
{
vis[e.to] = ;
d[e.to] = d[x] + ;
Q.push(e.to);
}
}
}
return vis[t];
} int DFS(int x, int a)
{
if (x == t || a == )
return a;
int flow = , f;
for (int &i = cur[x]; i<G[x].size(); i++)
{
Edge e = edges[G[x][i]];
if (d[x]+ == d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>)
{
edges[G[x][i]].flow+=f;
edges[G[x][i] ^ ].flow-=f;
flow+=f;
a-=f;
if(a==) break;
}
}
if(!flow) d[x] = -;
return flow;
} int dinic(int s, int t)
{
int flow = ;
while (BFS())
{
memset(cur, , sizeof(cur));
flow += DFS(s, INF);
}
return flow;
} void D(int x,int y)
{
for(int i=;i<GG[x].size();i++)
{
if(GG[x][i]==y) continue;
if(q[GG[x][i]]) { FF=; return; }
q[GG[x][i]]=;
D(GG[x][i],x); if(FF ) return ;
q[GG[x][i]]=;
}
} int main()
{
while(~scanf("%d%d%d",&n,&m,&k))
{
init();
s=, t=n+m+;
for(int i=;i<=n;i++)
{
int x; scanf("%d",&x);
AddEdge(s,i,x);
}
for(int i=;i<=m;i++)
{
int x; scanf("%d",&x);
AddEdge(n+i,t,x);
} for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
AddEdge(i,n+j,k); dinic(s,t); bool fail=;
for(int i=;i<edges.size();i=i+)
{
if(edges[i].from==s && edges[i].flow<edges[i].cap) fail=;
if(edges[i].to==t && edges[i].flow<edges[i].cap) fail=;
} if(fail) printf("Impossible\n");
else
{
FF=; memset(vis,,sizeof vis); for(int i=;i<edges.size();i=i+)
{
if(edges[i].flow<edges[i].cap)
{
if(edges[i].from==s||edges[i].from==t) continue;
if(edges[i].to==s||edges[i].to==t) continue; GG[edges[i].to].push_back(edges[i].from);
}
} for(int i= ;i<=n ;i++)
{
memset(q,,sizeof q);
q[i]=; D(i,-);
if(FF) break;
} if(FF==)
{
printf("Not Unique\n");
continue;
} printf("Unique\n");
int now=;
for(int i=;i<edges.size();i=i+)
{
if(edges[i].from==s) continue;
if(edges[i].to==t) continue;
printf("%d",edges[i].flow);
if(now%m==) printf("\n");
else printf(" ");
now++;
}
}
} return ;
}
05-11 17:13