poj 3281 Dining 拆点构图+sap

缘起

继续浪费生命~ poj 3281 Dining

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
有F种食物,D种饮料.N头奶牛,只能吃某些种食物和饮料(但是最后只能吃其中特定的一种食物和特定的饮料)
一种食物被一头牛吃了之后,其余牛就不能吃了,要求输出最多分配能够满足的牛的数量

【输入】
第一行有N,F,D（1 ≤ N、F、D ≤ 100））三个整数接着2~N+1行代表第i头牛,前面两个整数是Fi与Di
(食物与饮料的种类数量),接着是食物的种类与饮料的种类

【输出】
最多多少头牛可以得到满足

【样例输入】
4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3

【样例输出】
3

【限制】
2s

拆点. 这个术语在【1】中有论述. 这里的拆点是将一头牛拆成2头牛. 这里建图方法如下

在这个图上跑sap, 最后答案就是最大流. 

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
#include <string.h>
//#define LOCAL

int n,f,d,t, head[105*4],cnt,pre[105*4], flow[105*4], level[105*4], gap[105*4];

struct Arc
{
	int from, to, nxt, cap;
}g[105+105*105*2<<1];

void addArc(int from, int to, int cap)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].cap = cap;
	head[from] = cnt++;
	g[cnt].from = to, g[cnt].to = from, g[cnt].nxt = head[to], g[cnt].cap = 0;
	head[to] = cnt++;
}

void readandbuild()
{
	scanf("%d%d%d", &n, &f, &d);
	t = n*2+f+d+1; // 炒鸡汇
	for (int i = 1; i<=f; i++)
	{
		addArc(0, i, 1);
	} // 炒鸡源到食物的弧
	for (int i = f+n*2+1; i<t; i++)
	{
		addArc(i, t, 1);
	} // 饮料到炒鸡汇的弧
	for (int i = f+1; i<=f+n; i++)
	{
		addArc(i, i+n,1);
	} // 牛和拆出的牛之间连的弧
	for(int i = 1; i<=n; i++)
	{
		int fi,di,x;
		scanf("%d%d", &fi, &di);
		while(fi--)
		{
			scanf("%d", &x);
			addArc(x, f+i, 1);
		} // 读取食物的数据,食物到牛
		while(di--)
		{
			scanf("%d", &x);
			addArc(f+n+i, x+f+n*2, 1);
		} // 读取饮料的数据, 拆出的牛到饮料
	}
}

int feasible(int cur)
{
	for (int h = head[cur], to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (g[h].cap>0 && level[cur]==level[to]+1)
		{
			return h;
		}
	}
	return -1;
}

void updata(int s,int t, int d)
{
	int h;
	while(t!=s)
	{
		h = pre[t];
		g[h].cap-=d;
		g[h^1].cap+=d;
		t = g[h].from;
	}
}

int retreat(int cur)
{
	int ans = t+1;
	for (int h = head[cur], to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (g[h].cap>0 && ans>level[to]+1)
		{
			ans = level[to]+1;
		}
	}
	return ans;
}

int sap(int s, int t)
{
	memset(level, 0, sizeof(level));
	memset(gap, 0, sizeof(gap));
	int ans = 0, cur=s, nxtArc, nxt;
	flow[s] = 0x3f3f3f3f;
	while(level[s]<=t)
	{
		nxtArc = feasible(cur);
		if (~nxtArc)
		{
			nxt = g[nxtArc].to;
			pre[nxt] = nxtArc;
			flow[nxt] = min(flow[cur], g[nxtArc].cap);
			cur = nxt;
			if (cur==t)
			{
				ans+=flow[t];
				updata(s,t,flow[t]);
				cur = s;
			}
		}
		else
		{
			if (!--gap[level[cur]])
			{
				return ans;
			}
			gap[level[cur]=retreat(cur)]++;
			if (cur!=s)
			{
				cur = g[pre[cur]].from;
			}
		}
	}
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(head, -1, sizeof(head));
	readandbuild(); // 读取数据并建图
	printf("%d\n", sap(0,t));
	return 0;
}

ac情况

Status Accepted
Memory 184kB
Length 2315
Lang C++
Submitted 2019-09-29 16:48:58
Shared
RemoteRunId 20910488

参考

【1】https://yfsyfs.github.io/2019/09/28/poj-2391-Ombrophobic-Bovines-%E4%BA%8C%E5%88%86-%E6%8B%86%E7%82%B9-floyd-%E6%9C%80%E5%A4%A7%E6%B5%81/