hdu - 4888 - Redraw Beautiful Drawings（最大流）

标签：blog   http   io   os   ar   for   on   2014   log   

题意：给一个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 
#include 
#include 
#include 

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  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 = 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 


hdu - 4888 - Redraw Beautiful Drawings（最大流）
标签：blog   http   io   os   ar   for   on   2014   log   
原文地址：http://blog.csdn.net/scnu_jiechao/article/details/40658221