社区讨论
网络流 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 条回复,欢迎继续交流。
正在加载回复...