ACM-ICPC Nanjing Onsite 2018 I. Magic Potion (最大流 Dinic）

ACM-ICPC Nanjing Onsite 2018 I. Magic Potion

题目

分析

Dinic 模板

对于网络流的题目，其实难点就在建图，建完图跑一边模板就 ok。

这道题如果没有药水的限制，直接连英雄和怪兽，建源点汇点，边容量都为 1 跑最大流即可。可是多了一个条件，有 k 个英雄可以选择两个怪兽，

另外建一个虚拟节点 R，源点连向它容量为 k，R 连向英雄容量为 1。相当于有 k 个英雄节点的入度为 2。

另外代码中用的前向星，不能像 vector 那样动态的加边，需要事先指名最大边数。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fuck(x) cout<<x<<endl
const int N = 1e5 + 10;
const ll mod = 1e9 + 7;

int n, m, k;
int h[N], to[N], ne[N], cap[N], flow[N], idx;	// 存图

struct dinic{
	int s, t, vis[N], d[N], cur[N];
	dinic() { memset(h, -1, sizeof(h)), idx = 0; }
	void add(int u, int v, int c){		// 每次加入弧 和 反向弧
		cap[idx] = c, flow[idx] = 0, to[idx] = v, ne[idx] = h[u], h[u] = idx++;
		cap[idx] = 0, flow[idx] = 0, to[idx] = u, ne[idx] = h[v], h[v] = idx++;
	}
	int bfs(){			// BFS 找层次图，直到层次图里面不包括终点 t
		memset(vis, 0, sizeof(vis));
		queue<int> q;
		q.push(s);
		d[s] = 0;
		vis[s] = 1;
		while(!q.empty()){
			int u = q.front();
			q.pop();
			for(int i = h[u]; ~i; i = ne[i]){
				int v = to[i];
				if(!vis[v] && cap[i] > flow[i]){
					vis[v] = 1;
					d[v] = d[u] + 1;
					q.push(v);
				}
			}
		}
		return vis[t];
	}
	int dfs(int x, int mm){			// 跑阻塞流，加入当前弧优化
		if(x == t || mm == 0)
			return mm;
		int ans = 0, f;
		for (int& i = cur[x]; ~i; i = ne[i]){
			int v = to[i];
			if(d[x] + 1 == d[v] && (f = dfs(v, min(mm, cap[i] - flow[i]))) > 0){
				flow[i] += f;
				flow[i^1] -= f;
				ans += f;
				mm -= f;
				if(mm == 0) break;
			}
		}
		return ans;
	}
	int maxflow(int x, int y, int num){
		s = x, t = y;
		int ans = 0;
		while(bfs()){
			for(int i = 0; i <= num; i++) cur[i] = h[i];
			ans += dfs(s, INF);
		}
		return ans;
	}
};

int main(){
	dinic a;
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1, t, x; i <= n; i++){
		a.add(0, i, 1);			// 源点连英雄
		a.add(n + m + 1, i, 1);	// 虚拟节点连英雄
		scanf("%d", &t);
		while(t--){
			scanf("%d", &x);
			a.add(i,n + x, 1);	// 英雄连怪兽
		}
	}
	for(int i = 1; i <= m; i++)	// 怪兽连汇点
		a.add(i+n, n + m + 2, 1);
	a.add(0, n + m + 1, k);		// 源点连虚拟节点
	printf("%d\n", a.maxflow(0, n + m + 2, n+m+10));	// 跑最大流
}