P3254 圆桌问题

题目链接：P3254 圆桌问题

题意

有来自 $m$ 个不同单位的代表参加一次国际会议。第 $i$ 个单位派出了 $ri$ 个代表。会议的餐厅共有 $n$ 张餐桌，第 $i$ 张餐桌可容纳 $ci$个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。

解析

匹配问题之三，多对多的匹配问题，解决问题方法还是建图。
$0$号:源点
$1$~$m$:代表单位
$m+1$ ~ $m+n$:代表桌子
$m$ + $n+1$号: 汇点

$1.$源点流向单位的流量为该单位的代表人数$ri$
$2.$每个单位最多可以向一张桌子派一个人，流量为$1$
$3.$每张桌子最多可以坐$ci$个人，所以每张桌子流向汇点流量为$ci$

看最终流量是否等于所有参会的人数即可，输出公司与餐桌连边流量为$0$的边（匹配上的）即可

代码

/*

*/
#include 
#include 
#include 
using namespace std;
const int N = 1000, M = 100000;

int n,m,s,t,head[N],tot = 1;//注意要从1开始 即第一条边存储在e[2]中
struct edge
{
	int to,nex,w;
}e[M];
void add(int to,int from,int w)
{
	e[++ tot].w = w;
	e[tot].to = to;
	e[tot].nex = head[from];
	head[from] = tot;
}

int dep[N];//用bfs分层
bool bfs()//判断是否还存在增广路
{
	queue<int>q;
	q.push(s);
	for(int i = 0; i <= n + m + 1; i ++) dep[i] = 0;
	dep[s] = 1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(int i = head[u]; i; i = e[i].nex){
			int v = e[i].to;
			if(e[i].w && !dep[v]){
				dep[v] = dep[u] + 1;
				if(v == t) return true;
				q.push(v);
			}
		}
	}
	return dep[t];
}

int dfs(int u,int inflow)//in为进入的流,源点的流无限大
{
	if(u == t)//到达汇点
		return inflow;//返回这一条增广路的流量
	int outflow = 0;
	for(int i = head[u]; i && inflow; i = e[i].nex)//还有残余流量
	{
		int v = e[i].to;
		if(e[i].w && dep[v] == dep[u] + 1)//只搜索下一层次的点，防止绕回或走反向边
		{
			int flow = dfs(v , min(e[i].w, inflow));//min选取边残余容量与入流残余的最小值
			e[i].w -= flow; //减去达到汇点的增广流量
			e[i ^ 1].w += flow; //反向边增加流量
			inflow -= flow; //入流减少相同的
			outflow += flow; //增广路增加流量
		}
	}
	if(outflow == 0) dep[u] = 0;//通过u点不能到达汇点，剪枝
	return outflow;
}
int main()
{
    scanf("%d%d",&m,&n);

    /*
    0号:源点
    1~m:代表单位
    m + 1 ~ m + n:代表桌子
    m + n + 1: 汇点
    */
    int sum = 0;
    for(int i = 1; i <= m; i ++){
        int cnt;
        scanf("%d",&cnt);
        sum += cnt;
        add(i, 0, cnt); // 源点流向单位的流量为该单位的代表人数ri
        add(0, i, 0);
        for(int j = 1; j <= n; j ++){
            add(j + m, i, 1); // 每个单位最多可以向一张桌子派一个人
            add(i, j + m, 0);
        }
    }

    for(int i = 1; i <= n; i ++){
        int cnt;
        scanf("%d",&cnt);
        add(m + n + 1, m + i, cnt); //每张桌子最多可以坐ci个人，所以每张桌子流向汇点流量为ci
        add(m + i, m + n + 1, 0);
    }

    s = 0;
    t = m + n + 1;

    int ans = 0;
    while(bfs()){
        ans += dfs(s, 200000);
    }

    if(ans < sum){
        printf("0\n");
        return 0;
    }
    printf("1\n");
    for(int i = 1; i <= m; i ++){
        for(int j = head[i]; j; j = e[j].nex){
            if(e[j].to < n + m + 1 && !e[j].w) printf("%d ",e[j].to - m);
        }
        puts("");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114