poj 1149 PIGS EK

缘起

继续学习最大流之EK算法~

分析

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
给出猪圈个数 m 和买家人数 n(买家是依次来的) 然后给出m个猪圈的猪的头数..
接下来 n 行给出A K1 K2 .. KA B(表示这个买家可以打开A个猪圈,这些猪圈的标号是K1,...,KA,并且该买家想
买B头猪) 例如 2 1 5 3 表示第i+1个用户 有2个猪圈的钥匙就是有第1个和第5个猪圈的钥匙,想买3头猪.
问最多能够卖出多少头. A 和B可能为0

有 M 个猪圈，每个猪圈里初始时有若干头猪。一开始所有猪圈都是关闭的。依
次来了 N 个顾客，每个顾客分别会打开指定的几个猪圈，从中买若干头猪。每
个顾客分别都有他能够买的数量的上限。每个顾客走后，他打开的那些猪圈中的
猪，都可以被任意地调换到其它开着的猪圈里，然后所有猪圈重新关上。问总共
最多能卖出多少头猪。（1 <= N <= 100, 1 <= M <= 1000）
举个例子来说。有 3 个猪圈，初始时分别有 3、 1 和 10 头猪。依次来了 3 个顾客，
第一个打开 1 号和 2 号猪圈，最多买 2 头；第二个打开 1 号和 3 号猪圈，最多买
3 头；第三个打开 2 号猪圈，最多买 6 头。那么，最好的可能性之一就是第一个
顾客从 1 号圈买 2 头，然后把 1 号圈剩下的 1 头放到 2 号圈；第二个顾客从 3
号圈买 3 头；第三个顾客从 2 号圈买 2 头。总共卖出 2+3+2=7 头。

【输入】
第一行有M和N,1 <= M <= 1000, 1 <= N <= 100, 人是从1到N编号的,猪圈是从1到M编号的.
然后是M行, 每行是猪圈的猪的数量. 范围在[0,1000]. 然后是N行，每行是人的数据.

【输出】
最多能销售几头猪

【样例输入】
3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

【样例输出】
7

【限制】
1s

此题的构图我没想到！！！

首先暴力建图. 本题的关键是买家是一个一个来的. 所以就测试数据而言暴力建图是有三轮交易的（因为有3个买家）. 每一轮三个猪圈（三个点）.首轮交易时, 炒鸡源到每个猪圈的弧的容量是猪圈中猪的数量. 而每个本轮交易打开的猪圈到买家都有一条容量为inf的弧. 每个买家到炒鸡汇的弧的容量是买家需要猪的数量. 而除了最后一轮交易外, 上一轮交易打开的猪圈到下一轮这些猪圈彼此都连有inf的弧. 表示上一轮交易打开的猪圈之间可以流动调配猪. 而且上一轮剩下的猪可以留到下一轮. 即如下图所示（没有标数字的弧就是inf容量的弧）

则改图的最大流就是答案. 但是此图的节点数量是O(n*m)的. 因为n轮，每轮大约m个节点. 即达到了10w的节点数量. 在这样的图上跑ek算法是很低效的. 所以我们得想办法给这个图瘦身. 掌握下面三条规则

  1. 流量去向一样的节点可以合并.
  2. 流量来源一样的节点可以合并.
  3. 如果v只有u作为来源，而且u->v的弧容量为inf, 则u和v可以合并.

所以我们把图1复刻一下

图2的蓝色部分的左边的1和2可以合并为u（规则1），蓝色部分右边的1和2可以合并为v（规则2）. u和v可以合并（规则3）. 所以变成

再根据规则3，图3的蓝色点和顾客1以及猪圈2可以合并. 即最后流网络缩减为

所以我们就知道如何建图了.

首先读入所有的猪圈中猪的数量. 然后依次读取买家的数据. 对于一个猪圈第一个买家, 连一条源到该买家的弧. 弧的容量是该猪圈的容量. 如果一个买家比较吊，是很多猪圈的第一个买家，则增加源到该买家的弧的容量即可（但是实际并没有这么做,还是a掉了）. 如果一个买家A不是某猪圈的第一个买家，而是后面的买家. 则维护各个猪圈最后那个买家. 然后只需连一条inf的弧从最后的买家到A即可. 最后, 每个买家到汇都要连接一条弧. 弧的容量是该买家需要的猪的数量.

一旦图建出来了，则代码就好写了——直接在此图上跑ek即可.

代码没写注释，注释参见【1】

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
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
//#define LOCAL

const int maxn = 110, maxm = 1010, inf = 0x3f3f3f3f;
int n,m, p[maxm], head[maxn], cnt, last[maxm],pre[maxn],flow[maxn]; // p是每个猪圈中猪的数量, last维护了每个猪圈最后的买家编号

struct Arc
{
	int from,to,nxt,cap;
}g[maxn*maxn];

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 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 bfs(int s, int t)
{
	memset(pre, -1, sizeof(pre));
	queue<int> q;
	flow[s] = inf;
	q.push(s);
	while(!q.empty())
	{
		int front = q.front();
		q.pop();
		if (front == t)
		{
			updata(s,t,flow[t]);
			return flow[t];
		}
		for (int h = head[front],to; ~h; h = g[h].nxt)
		{
			to = g[h].to;
			if (!~pre[to] && g[h].cap>0)
			{
				pre[to] = h;
				flow[to] = min(flow[front], g[h].cap);
				q.push(to);
			}
		}
	}
	return 0;
}

int ek(int s,int t)
{
	int ans = 0;
	while(1)
	{
		int d = bfs(s,t);
		if (!d)
		{
			return ans;
		}
		ans+=d;
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\ac.out", "w", stdout);
#endif
	scanf("%d%d", &m,&n);
	memset(head, -1, sizeof(head));
	for (int i = 1; i<=m; i++)
	{
		scanf("%d", p+i);
	}
	for (int i = 1,k,x;i<=n;i++)
	{
		scanf("%d", &k);
		while(k--)
		{
			scanf("%d", &x);
			if (!last[x])
			{
				addArc(0, i, p[x]);	// 注意, 这里并没有像上面说的那样合并弧的容量
			}
			else
			{
				addArc(last[x], i, inf);
			}
			last[x] = i;
		}
		scanf("%d", &k);
		addArc(i, n+1, k);
	} // 建图完毕
	printf("%d\n", ek(0,n+1));
	return 0;
}

ac情况

Status Accepted
Time 94ms
Memory 580kB
Length 1786
Lang G++
Submitted 2019-09-26 11:22:54
RemoteRunId 20899632

参考

【1】https://yfsyfs.github.io/2019/09/25/poj-1273-Drainage-Ditches-EK%E6%A8%A1%E6%9D%BF%E9%A2%98-%E6%9C%80%E5%A4%A7%E6%B5%81/