学步园

题意：给一个N行M列的数字矩阵的行和以及列和，每个元素的大小不超过K，问这样的矩阵是否存在，是否唯一，唯一则求出各个元素N(1 ≤ N ≤ 400) , M(1 ≤ M ≤ 400), K(1 ≤ K ≤ 40)。

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4888

——>>建图：

1）超级源S = 0，超级汇T = N + M + 1；

2）S到每个行和各连一条边，容量为该行行和；

3）每个行和到每个列和各连一条边，容量为K；

4）每个列和到 T 各连一条边，容量为该列列和。

一个行到所有列连边，为的是让该行分流多少给各个列，正是该行某列元素的大小。。

所以，如果 S 到 T 的最大流 == 所有元素的和，则说明有解。。

残量网络中的行列结点之间如果有长度 > 2 的环（自环长度为2，但无法调整流量），则说明这个环中的流量可以调整，使得达到最大流时该环上的流量不唯一，即矩阵不唯一。。

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>

using std::min;
using std::queue;

const int MAXN = 400 * 2 + 10;
const int MAXM = 400 * 400 + 2 * MAXN;
const int INF = 0x3f3f3f3f;

struct EDGE
{
    int to;
    int cap;
    int flow;
    int nxt;
} edge[MAXM << 1];

int N, M, K;
int sum;
int S, T;
int hed[MAXN], ecnt;
int cur[MAXN], h[MAXN];
bool impossible, bUnique;

void Init()
{
    impossible = false;
    bUnique = true;
    ecnt = 0;
    memset(hed, -1, sizeof(hed));
}

void AddEdge(int u, int v, int cap)
{
    edge[ecnt].to = v;
    edge[ecnt].cap = cap;
    edge[ecnt].flow = 0;
    edge[ecnt].nxt = hed[u];
    hed[u] = ecnt++;
    edge[ecnt].to = u;
    edge[ecnt].cap = 0;
    edge[ecnt].flow = 0;
    edge[ecnt].nxt = hed[v];
    hed[v] = ecnt++;
}

bool Bfs()
{
    memset(h, -1, sizeof(h));
    queue<int> qu;
    qu.push(S);
    h[S] = 0;
    while (!qu.empty())
    {
        int u = qu.front();
        qu.pop();
        for (int e = hed[u]; e != -1; e = edge[e].nxt)
        {
            int v = edge[e].to;
            if (h[v] == -1 && edge[e].cap > edge[e].flow)
            {
                h[v] = h[u] + 1;
                qu.push(v);
            }
        }
    }

    return h[T] != -1;
}

int Dfs(int u, int cap)
{
    if (u == T || cap == 0) return cap;

    int flow = 0, subFlow;
    for (int e = cur[u]; e != -1; e = edge[e].nxt)
    {
        cur[u] = e;
        int v = edge[e].to;
        if (h[v] == h[u] + 1 && (subFlow = Dfs(v, min(cap, edge[e].cap - edge[e].flow))) > 0)
        {
            flow += subFlow;
            edge[e].flow += subFlow;
            edge[e ^ 1].flow -= subFlow;
            cap -= subFlow;
            if (cap == 0) break;
        }
    }

    return flow;
}

int Dinic()
{
    int maxFlow = 0;

    while (Bfs())
    {
        memcpy(cur, hed, sizeof(hed));
        maxFlow += Dfs(S, INF);
    }

    return maxFlow;
}

void Read()
{
    int r, c;
    int rsum = 0, csum = 0;

    S = 0;
    T = N + M + 1;
    for (int i = 1; i <= N; ++i)
    {
        scanf("%d", &r);
        rsum += r;
        AddEdge(S, i, r);
    }
    for (int i = 1; i <= M; ++i)
    {
        scanf("%d", &c);
        csum += c;
        AddEdge(i + N, T, c);
    }

    if (rsum != csum)
    {
        impossible = true;
        return;
    }

    sum = rsum;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = M; j >= 1; --j)
        {
            AddEdge(i, j + N, K);
        }
    }
}

void CheckPossible()
{
    if (impossible) return;
    if (Dinic() != sum)
    {
        impossible = true;
    }
}

bool vis[MAXN];
bool CheckCircle(int x, int f)
{
    vis[x] = true;
    for (int e = hed[x]; e != -1; e = edge[e].nxt)
    {
        if (edge[e].cap > edge[e].flow)
        {
            int v = edge[e].to;
            if (v == f) continue;
            if (vis[v]) return true;
            else
            {
                if (CheckCircle(v, x)) return true;
            }
        }
    }
    vis[x] = false;
    return false;
}

void CheckUnique()
{
    if (impossible) return;
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= N; ++i)
    {
        if (CheckCircle(i, -1))
        {
            bUnique = false;
            return;
        }
    }
}

void Output()
{
    if (impossible)
    {
        puts("Impossible");
    }
    else if (!bUnique)
    {
        puts("Not Unique");
    }
    else
    {
        puts("Unique");
        for (int i = 1; i <= N; ++i)
        {
            for (int e = hed[i], j = 1; e != -1 && j <= M; e = edge[e].nxt, ++j)
            {
                printf("%d", edge[e].flow);
                if (j < M)
                {
                    printf(" ");
                }
            }
            puts("");
        }
    }
}

int main()
{
    while (scanf("%d%d%d", &N, &M, &K) == 3)
    {
        Init();
        Read();
        CheckPossible();
        CheckUnique();
        Output();
    }

    return 0;
}