UVA 10249 The Grand Dinner

时间：2010-10-09 来源：晓天

晚宴桌子分配，同一个队伍的人不能坐在同一个桌子旁边。求存不存在这样的分配方案，存在则输出方案。

典型的最大流。

建图方法：从源点连一条边到所有的队伍，流量为队伍成员数量；

从所有桌子连一条边到汇点，流量为桌子容量；

从每个队伍连一条边到每一个桌子，流量为1，表示这个队伍到这个桌子只能去一个人。

求最大流，若最大流量等于所有人数，则表示可行，否则不可行。

输出方案可以从剩余网络中得到。若某一个队伍到某一个桌子的剩余流量为0，那么表示这个队伍中的一个人可以坐到这个桌子旁边。

我使用的是dinic的数组实现，方便输出结果。

代码

/* 
 * File:   Max_flow UVA 10249 The Grand Dinner
 * Author: xiaotian @ hnu
 * Created on 2010年10月9日, 上午11:26
 * 题解：数组实现，dinic 使用邻接矩阵 点从1开始到n
 */
#include <iostream>
#include <stdio.h>
#include <queue>
#include <list>
#define N 205
#define E 205
#define inf 0x7ffffff
using namespace std;
int g[N][N]; /*剩余流*/
bool vis[N]; /*标记数组*/
int level[N];
int p, n, m; /*顶点数，边数*/
int src, sink; /*scr源 sink汇*/
int sum0, sum1;

int build() //初始化图(包括写入边 初始化边数与点数)
{
    int k = n + m + 2, a, flag = 1;
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= k; j++) {
            g[i][j] = 0;
        }
    }
    src = 1;
    sink = k;
    sum0 = sum1 = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a);
        if (a > m) flag = 0;
        sum0 += a;
        g[1][1 + i] = a;
    }
    for (int i = 1; i <= m; i++) {
        scanf("%d", &a);
        sum1 += a;
        g[1 + n + i][k] = a;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            g[i + 1][1 + n + j] = 1;
    p = n;
    n = k;
    return flag;
}

int find(int x) {
    for (int i = 1; i <= n; i++) {
        if (g[x][i] != 0 && level[i] == level[x] + 1)
            return i;
    }
    return 0;
}

int bfs() {
    queue<int> que;
    bool flag = 0;
    for (int i = 1; i <= n; i++) {
        level[i] = inf;
        vis[i] = false;
    }

    que.push(src);
    vis[src] = true;
    level[src] = 0;

    while (!que.empty()) {
        int temp = que.front();
        que.pop();
        for (int i = 1; i <= n; i++) {
            if (g[temp][i] != 0 && !vis[i]) {
                vis[i] = true;
                level[i] = level[temp] + 1;
                que.push(i);
            }
        }
        if (temp == sink)
            flag = true;
    }
    return flag;
}

int dinic() //dinic 返回最大流值
{
    int u, v, capflow, last;
    list<int> path;
    list<int>::iterator its;
    int maxflow = 0;
    while (bfs()) {
        path.clear();
        path.push_back(src);
        while (find(src) != 0) {
            u = path.back();
            if (u != sink) {
                if (v = find(u))
                    path.push_back(v);
                else {
                    path.pop_back();
                    level[u] = inf;
                }
            } else {
                capflow = inf;
                for (its = path.begin(); its != path.end(); its++) {
                    u = *its;
                    if ((++its) == path.end())
                        break;
                    v = *its;
                    if (g[u][v] < capflow)
                        capflow = g[u][v];
                    --its;
                }
                last = -1;
                maxflow += capflow;
                for (its = path.begin(); its != path.end(); its++) {
                    u = *its;
                    if ((++its) == path.end())
                        break;
                    v = *its;
                    g[u][v] -= capflow;
                    g[v][u] += capflow;
                    if (g[u][v] == 0 && last == -1)
                        last = u;
                    --its;
                }
                while (path.back() != last)
                    path.pop_back();
            }
        }
    }
    return maxflow;
}

void print() {
    for (int i = 1; i <= p; i++) {
        for (int j = 1; j <= m; j++)
            if (g[i + 1][1 + p + j] == 0) printf("%d ", j);
        puts("");
    }
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n == 0 && m == 0) return 0;
        int k = build();
        if (k == 0 || sum0 > sum1) {
            puts("0");
            continue;
        }
        k = dinic();
        if (k >= sum0) {
            puts("1");
            print();
        } else puts("0");
    }
}