社区讨论

网络流 40 pts 求助

P2891[USACO07OPEN] Dining G参与者 3已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@lo8bbps8
此快照首次捕获于
2023/10/27 15:49
2 年前
此快照最后确认于
2023/10/27 15:49
2 年前
查看原帖
RT,思路就是源点 -> 食物,食物 -> 牛,把牛拆点容量为 1,牛 -> 饮料,饮料 -> 汇点。WA #2,5,7,8,9,10。
C
#include <bits/stdc++.h>
using namespace std;
int n, m, ans, q, nx, ny, s, t, p, x, y, h[510], dep[510], vis[510];
struct node{
	int x, y, z, next;
}d[200010];
void add(int x, int y, int z){
	d[++p].y = y, d[p].z = z, d[p].next = h[x], h[x] = p;
}
int bfs(){
	memset(dep, 0, sizeof(dep));
	queue <int> q;
	q.push(s); dep[s] = 1;
	while (!q.empty()){
		int x = q.front(); q.pop();
		for (int i=h[x]; i; i=d[i].next){
			int y = d[i].y;
			if (d[i].z != 0 && dep[y] == 0){
				dep[y] = dep[x] + 1;
				q.push(y);
			}
		}
	}
	return dep[t];
}
int dfs(int x, int flow){
	if (x == t) return flow;
	vis[x] = 1;
	int out = 0;
	for (int i=h[x]; i; i=d[i].next){
		int y = d[i].y;
		if (d[i].z && dep[y] == dep[x] + 1){
			int now = dfs(y, min(d[i].z, flow));
			d[i].z -= now, d[i^1].z += now;
			flow -= now, out += now;
		}
	}
	if (!out) dep[x] = 0;//没有出流 
	return out;
}
int main(){
	scanf ("%d%d%d", &n, &m, &q);
	for (int i=1; i<=n; i++){
		scanf ("%d%d", &nx, &ny);
		for (int j=1; j<=nx; j++){//食物 
			scanf ("%d", &x);
			add(2*n+x, i, 1);
			add(i, 2*n+x, 0);
		}
		for (int j=1; j<=ny; j++){//饮料 
			scanf ("%d", &x);
			add(n+i, 2*n+m+x, 1);
			add(2*n+m+x, n+i, 0);
		}
	}
	for (int i=1; i<=m; i++){
		add(0, 2*n+i, 1);
		add(2*n+i, 0, 0);
	}
	for (int i=1; i<=q; i++){
		add(2*n+m+i, 2*n+m+q+1, 1);
		add(2*n+m+q+1, 2*n+m+1, 0);
	}
	for (int i=1; i<=n; i++){
		add(i, n+i, 1);
		add(n+i, i, 0);
	}
	s = 0, t = 2*n + m + q + 1;
	while (bfs()){
		ans += dfs(s, 1e9);
	}
	printf ("%d\n", ans);
	return 0;
}
/*
牛的编号:1~n -> i
拆点牛编号:n+1 ~ 2n -> n+i 
食物的编号:2n+1~2n+m -> 2n+i
饮料的编号:2n+m+1~2n+m+q -> 2n+m+i
源点:0
汇点:2n+m+q+1 
*/

回复

4 条回复,欢迎继续交流。

正在加载回复...