蒟蒻求助Dinic,WA#2#5#6#10
查看原帖
蒟蒻求助Dinic,WA#2#5#6#10
213218
蒟蒻CGZ楼主2021/3/22 22:42

RTRT,有巨佬能帮忙看一下吗?感谢

思路是:超级源点 0 -> 食物 1~f -> 牛(入点) f+1~f+n -> 牛(出点) f+n+1~f+2*n -> 饮料 f+2*n+1~f+2*n+d -> 超级汇点

代码如下,变量名尽量和题目中的差不多:

#include <bits/stdc++.h>
using namespace std;

const int N = 10010;
int head[N], cnt = 0;
struct Edge {
	int to, w, next;
} e[N << 1];
int n, f, d, lev[N];
int S, T;

inline void add(int u, int v, int w) {
	e[++ cnt].to = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

inline bool Bfs() {
	queue<int> q;
	for (int i = S; i <= T; ++ i) lev[i] = -1;
	q.push(S); lev[S] = 0;
	while(!q.empty()) {
		int u = q.front(); 
		q.pop();
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].to;
			if(e[i].w && lev[v] == -1) {
				lev[v] = lev[u] + 1;
				q.push(v);
				if(v == T) return true;
			}
		}
	}
	return false;
}

inline int Dinic(int u, int flow) {
	if (u == T)
		return flow;
	int res = 0, delta;
	for (int i = head[u]; i; i = e[i].next) {
		int v = e[i].to;
		if (e[i].w && lev[u] < lev[v]) {
			delta = Dinic(v, min(e[i].w, flow - res));
			if (delta) {
				e[i].w -= delta; 
				e[i ^ 1].w += delta;
				res += delta;
				if(res == flow) break;
			}
		}
	}
	if(res != flow) lev[u] = -1;
	return res;
}

int main() {
	scanf("%d%d%d", &n, &f, &d);
	
	S = 0;
	T = f + 2 * n + d + 1;
	for (int i = 1; i <= f; ++ i)
		add(S, i, 1), add(i, S, 0);
	for (int i = f + 2 * n + 1; i <= f + 2 * n + d; ++ i)
		add(i, T, 1), add(T, i, 0);
	
	for (int a1, a2, b, i = 1; i <= n; ++ i) {
		add(f + i, f + n + i, 1);
		add(f + n + i, f + i, 0);
		scanf("%d%d", &a1, &a2);
		for (int j = 1; j <= a1; ++ j) {
			scanf("%d", &b);
			add(b, f + i, 1); add(f + i, b, 0);
		}
		for (int j = 1; j <= a2; ++ j) {
			scanf("%d", &b);
			add(f + n + i, f + 2 * n + b, 1); add(f + 2 * n + b, f + n + i, 0);
		}
	}
	int ans = 0;
	while(Bfs())
		ans += Dinic(S, INT_MAX);
	printf("%d\n", ans);
	return 0;
}

2021/3/22 22:42
加载中...