语言漩涡

thirtiseven 的博客

0%

最小割 PA2006 Travel Agency

Posted on Edited on

题意

有 n 个人想去旅行。

第 i 个人愿意为自己的旅行付出 块钱。

第 i 个人还有 个要求，每个要求由一个数对 定义。意思是如果第 i 个人去旅行，那么第 个人也要去，否则就要给他优惠 块钱。

求使旅行社获得最大利润的一种方案。

输入输出

第一行输入一个n

下面每行输入 和 组数

输出一个数 k ，第二行有 k 个数，表示方案。

样例

1
2
3
4
5
4
5 0
6 2 1 10 3 1
-10 0
1 2 1 10 2 10
1
2
3
1 2 4

解法

复习一下最大流最小割定理。假设有一个网络，网络中的每条边有一个容量。有一个点叫源点 s，一个点叫汇点 t。一个流是指一种流量的分配，其中：每条边的流量不超过容量；汇入每个普通点的流量和流出每个普通点的流量相等；源点流出的流量等于汇点流入的流量。最大流是要求从源点流向汇点的流量最大的流。一个割是一个边集，使得从原图中删除这个边集s和t就互不连通。最小割指的是删掉的边的容量之和最小的割。最大流最小割定理告诉我们：对于一个网络，从源点到目标点的最大的流量等于最小割的每一条边的和。

首先，为了简化，我们假设没有的顾客。建立一个辅助图G。设每个顾客为一个节点，建立一个源点和汇点，对每个 的顾客 ，从 s 到 连一条容量为 的边，对每个 的顾客 ，从 到 t 连一条容量为 的边。对于顾客的每个要求 ，从 到 连一条容量为 的边。对样例这样建图的示例如下：

Travel Agency

考虑旅行社的选择对总利润的贡献，先假设目前选择了所有 的顾客：

  • 如果没有选择一个 的顾客，那旅行社就损失了 块钱。
  • 如果选择了一个 的顾客，那旅行社就损失了 块钱。
  • 如果某个顾客的要求没有满足，那么旅行社就损失了 块钱。

设 W 是获得利润的上限（即所有 大于 0 的 之和），OPT是能够的最大利润，我们有两条引理。记 的顾客集合为 ， 的顾客集合为 ，A 为所有顾客条件的集合。

引理1 图 G 的最小割小于等于 W - OPT .

证明：设 X 为旅行社获得最大利润时顾客的集合。定义集合 S： 注意到集合S就是我们上述描述条件的集合，于是这些边的流量和等于 W - OPT。特殊的，样例中的集合 S 只包括 v2 到 v3 一条边。

让我们先假设 S 不是一个 G 的割集。令 是一条从 s 到 t 到路径，并且这个路径不包含任何 S 中的边。根据图 G 的定义，所有来自s的边都连着一个 中的点，所有指向t的点都来自于一个 中的点。否则边就是一条从 中的点指向 中的点的边。于是，我们知道 被选择了，相似的， 没有被选择。 于是，这条路径中必然存在一条边 ，满足 被选择了而 没有被选择。这条边必然存在于 S 中。所以 S 肯定是 G 的一个割集。所以图 G 的最小割必然小于等于 W-OPT，得证。

引理2 图G的最小割大于等于 W-OPT.

证明：假设 S 是任意一个最小割。设应该被选择顾客的集合为 X（如下图），集合X包含：

  • 每个满足边 (s, v) 不属于集合 S 的
  • 每个满足边 (v, t) 属于集合 S 的
Travel Agency2

设 为最小割中容量的和。为了证明引理，我们需要证明每一个没有被满足的要求都属于集合 S。

考虑这个命题的反面，存在一个第 i 个用户的要求没有被满足，并且对应的边不属于 S。假设 和 ，考虑在下图中描述的下列情况。 我们发现，对于每一种情况，G 关于 S 的补图中存在一条从 s 到 t 的 路径，这和割集的定义相矛盾：

Travel Agency3

  1. 既然 ，那么有 。因为我们要最小化 S，所以 S 的补图中肯定存在一条从 s 到 的路径。又由于 于是 S 的补图中也肯定存在一条从 s 到 的路径。根据集合 X 的定义和 的假设，我们推断出 ，于是补图中肯定存在一条从 s 到 t 的路径，产生了矛盾。

  2. 相似的，我们推测补图中存在一条从 到 的路径，相似的，因为要最小化 S 的容量和，所以 S 的补图中肯定存在一条从 到 t 的路径。于是补图中肯定存在一条从 s 到 t 的路径，产生了矛盾。

  3. 在这种情况下 和 都不属于集合 S，所以在补图中存在一条从 s 到 t 的路径，产生了矛盾。

  4. 根据 X 的定义， 不属于集合 S，考虑到 S 是最小割，我们推测补图中存在一条从 到 t 的路径。考虑到 不在集合 S 中，所以就存在一条从 s 到 t 的路径，产生了矛盾。

因此，引理得证。综合这两条引理，我们发现最大利润就是 W-最小割。根据最小割最大流定理，我们可以通过计算图 G 的最大流来求出其最小割。从而解决整个问题。如果使用 Dinic，复杂度是

但是有一个问题还没有解决。此前我们假设不存在 。但实际上这个假设是不必要的。不妨认为每个 的 实际上是一个极小的 。则旅行社选择他们获得的利润也不会超过 0.5 元。不妨把这些顾客全部归入 。如果有多个最小割存在，我们选择边数最少的最小割。

代码

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
#include <iostream>
#include <algorithm>
#include <queue> 
#include <vector> 
#include <cassert>

using ll = long long;

const ll maxn = 1000+7;
const ll inf = 1e9+7; 
const ll mod = 2e4;

struct Edge { 
	ll c;
	ll f;
	ll v;
	ll flip;
	Edge(ll v, ll c, ll f, ll flip) : v(v), c(c), f(f), flip(flip) {} 
};

class Dinic { 
private:
	bool b[maxn];
	ll a[maxn];
	ll p[maxn], cur[maxn], d[maxn];
	std::vector<Edge> G[maxn];
public:
	ll vis[maxn];
	ll s, t;
	void Init(ll n) { 
		for(ll i=0; i<=n; ++i)
			G[i].clear();
		std::fill(vis, vis+maxn, 0);
	}
	void AddEdge(ll u, ll v, ll c) { 
		G[u].push_back(Edge(v, c, 0, G[v].size())); 
		G[v].push_back(Edge(u, 0, 0, G[u].size()-1)); //使用无向图时将0改为c即可
	}
	bool BFS() { 
		ll u, v;
		std::queue<ll> q; 
		std::fill(b, b+maxn, 0); 
		q.push(s);
		d[s] = 0;
		b[s] = 1; 
		while (!q.empty()) {
			u = q.front();
			q.pop();
			for (auto it : G[u]) {
				Edge &e = it; 
				if(!b[e.v] && e.c > e.f){
					b[e.v] = 1; 
					d[e.v] = d[u] + 1; 
					q.push(e.v);
				} 
			}
		}
		return b[t]; 
	}
	ll DFS(ll u, ll a){ 
		if(u==t || a==0)
			return a; 
		ll flow = 0, f;
		for (ll i = cur[u]; i<G[u].size(); ++i){ 
			Edge &e = G[u][i];
			if (d[u]+1 == d[e.v] && (f = DFS(e.v, std::min(a, e.c - e.f))) > 0) { 
				a -= f;
				e.f += f; 
				G[e.v][e.flip].f -= f; 
				flow += f;
				if (!a) break;
			} 
		}
		return flow; 
	}
	ll MaxFlow(ll s, ll t){ 
		ll flow = 0;
		this->s = s; 
		this->t = t; 
		while (BFS()) {
			std::fill(cur, cur+maxn, 0);
			flow += DFS(s, inf); 
		}
		return flow; 
	}
	void gao(ll u) {
		vis[u] = 1;
		for (ll i = 0; i < G[u].size(); i++) {
			ll v = G[u][i].v;
			if (vis[v] || G[u][i].f > 0) {
				continue;
			}
			gao(v);
		}  
	}
};

Dinic flow;
ll n, x[maxn], k, aa, bb;
std::vector<ll> ans;

signed main() {  
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cin >> n;	
	flow.Init(n+3);
	ll s = 0, t = n+1;
	for (ll i = 1; i <= n; i++) {
		std::cin >> x[i] >> k;
		if (x[i] >= 0) {
			flow.AddEdge(s, i, x[i]*mod+1);
		} else if (x[i] < 0) {
			flow.AddEdge(i, t, (-x[i])*mod+1);
		}
		for (ll j = 0; j < k; j++) {
			std::cin >> aa >> bb;
			flow.AddEdge(i, aa, bb*mod+1);
		}
	}
	flow.MaxFlow(s, t);
	flow.gao(s);
	ans.clear();
	for (ll i = 1; i <= n; i++) {
		if (x[i] >= 0) {
			if (!(flow.vis[s]&&!flow.vis[i] || flow.vis[i]&&!flow.vis[s])) {
				ans.push_back(i);
			}
		} else {
			if (flow.vis[t]&&!flow.vis[i] || flow.vis[i]&&!flow.vis[t]) {
				ans.push_back(i);
			}
		}
	}
	std::sort(ans.begin(), ans.end());
	std::cout << ans.size() << "\n";
	for (ll i = 0; i < ans.size(); i++) {
		std::cout << ans[i] << " \n"[i==ans.size()-1];
	}
}

吐槽

这个代码没过... 放弃了... 不想再看到它了...

网上找不到题解，在 szkopul 上下到了数据，本地跑得非常逼真，交上去 RE 了一年。去韩国 OJ 交，也 RE，但是这两边的 RE 是本质不同的... 大力assert了一下，感觉两边数据都是错的... 但是szkopul 上过了20个人了，就很离谱，我怀疑是我读入方式有问题，它可能不是标准输入输出，之类的，搞不清楚，在一堆波兰语和韩语里面的东西挣扎... 非常痛苦... 我都已经退役了... 偶尔写写算法题应该是一件快乐的事情... 为什么事情会变成这样...

关于要怎么输出割集，牛逼网友教了教我，是从 S 出发dfs 一下，没满流的边不走，搞出一个类似联通块一样的东西，然后对每一条边判一下它是不是在两个不同的联通分量里面。很有道理，学到很多...

关于怎么求边数最小的割集，牛逼网友又教了教我，是把容量全部改成 边数 ，然后求出来的最小割就自然是边数最小的，然后模一模就能得到各种信息了。听起来非常有道理，奥妙重重，我一辈子想不出来这种操作。

然后关于这个题，我发现它就是一个复杂版本的最大权闭合子图... 最大权闭合子图是说，每个顾客都钦定了一些朋友，要选一起选，要么就都别选... 做法就是建图的时候要求的容量改成无穷大...

然后就都大力糊了上去，感觉自己非常对，对着数据本地测了一年，感觉也非常对，但是这你妈的为什么过不了啊？抑郁了啊？感觉自己应该停止做传统算法题啊？有没有牛逼网友带我打打kaggle啊？