TIOJ-2134

發表於 更新於 Disqus：

從前從前，有 $N$個英雄和 $M$隻怪物住在一個島上，怪物們最近變得很兇殘，所以英雄們決定要消滅怪物，第$i$個英雄只能消滅 $M_i$這個集合裡的其中一隻怪物。周逸身為英雄團的軍師，研發出了一種藥水，可以加強英雄的能力，一罐藥水可以使一個英雄多消滅一隻怪物。由於藥水有些副作用，一個英雄最多只能服用一瓶藥水，現在有$K$瓶藥水，請幫助周逸算出要最好的策略下，英雄團最多可以消滅多少隻怪物。

$N, M, K\le 500, |M_i|\le M$

這題是最大流應用。
該怎麼建模呢?
根據題目條件一個一個看:

  • 每個英雄只能擊到一個怪物: 從源點連容量為1的邊到每個英雄，每個英雄再連容量為1的邊到每個他可以消滅的怪物上。
  • 每個英雄只能用最多一瓶藥水，藥水可以讓英雄多消滅一個: 從源點連流量為$K$的邊到藥水上，藥水再連容量為1的邊到每個英雄。
  • 問最多能消滅幾隻怪物: 每個怪物連一條流量為1的邊到匯點。

這樣最大流就會是可以消滅的怪物數量了。
用dinic的複雜度為$\mathcal{O}(V^2E)=\mathcal{O}((N+M)^2NM)$

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
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
 
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

const int N = 1007;
struct DinicAlgorithm {
	struct edg {
		int v, cap, to;
	};
	vector<edg> edge[N];
	int dis[N], n, s, t, iter[N];
	void init(int _n, int _s, int _t) {
		n = _n; s = _s; t = _t;
	}
	void add_edge(int u, int v, int f) {
		edge[u].push_back({v, f, edge[v].size()});
		edge[v].push_back({u, 0, edge[u].size() - 1});
	}
	void bfs() {
		memset(dis, 0x3f, sizeof dis);
		dis[s] = 0;
		queue<int> que;
		que.push(s);
		while(!que.empty()) {
			int u = que.front();
			que.pop();
			for(const auto &[v, c, r] : edge[u]) {
				if(c > 0 && dis[v] > dis[u] + 1) {
					dis[v] = dis[u] + 1;
					que.push(v);
				}
			}
		}
	}
	int dfs(int u, int f) {
		int res = 0;
		if(u == t)
			return f;
		for(; iter[u] < edge[u].size(); iter[u]++) {
			auto &[v, cap, rev] = edge[u][iter[u]];
			if(!cap || dis[v] != dis[u] + 1)
				continue;
			int w = dfs(v, min(f, cap));
			if(w > 0) {
				f -= w;
				res += w;
				cap -= w;
				edge[v][rev].cap += w;
				if(!f)
					break;
			}
		}
		return res;
	}
	int flow() {
		int res = 0;
		while(1) {
			bfs();
			if(dis[t] == INF)
				break;
			memset(iter, 0, sizeof iter);
			res += dfs(s, INF);
		}
		return res;
	}
} dinic;

signed main() { EmiliaMyWife
	int n, m, k;
	cin >> n >> m >> k;
	dinic.init(n + m + 3, n + m + 1, n + m + 2);

	for(int i = 0, a, b; i < n; i++) {
		cin >> a;
		dinic.add_edge(n + m + 1, i, 1);
		while(a--) {
			cin >> b;
			dinic.add_edge(i, n + b - 1, 1);
		}
		dinic.add_edge(n + m, i, 1);
	}
	for(int i = 0; i < m; i++)
		dinic.add_edge(n + i, n + m + 2, 1);
	dinic.add_edge(n + m + 1, n + m, k);
	cout << dinic.flow() << '\n';
}