pid=4888">http://acm.hdu.edu.cn/showproblem.php?pid=4888

加入一个源点与汇点，建图例如以下：

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;

}