【LG-P2891[USACO07OPEN]】Dining G

pldzy · 2022-02-11 20:16:27 · 个人记录

传送门：P2891 [USACO07OPEN]Dining G

最大网络流：拆点的运用

针对题目条件，我们可有一下分析：

1. “一头奶牛只和一种饮料且只吃一种食物”

这个条件意在限定一个点的流量。

所以，就可以将代表一头奶牛的每一个节点拆分成两个节点，入点和出点。这头奶牛喜欢的所有食物连向入点，自出点连向它喜欢的所有饮料。并且自入点到出点的路径容量为 1。

2. “每一份食物和一份饮料只能给一头奶牛吃”

满足这个条件，只需要将源点连向食物的边的容量设为 1，将饮料连向汇点的容量设为 1 即可。

这样就能保证自食物点或饮料店流出的流量不大于 1 了。

代码 + 注释

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

#define maxn 505
#define maxm 200005
#define rep(i, a, b) for(int i = a; i <= b; ++i)
int n, f, d, s, t;
int cnt = 1, hd[maxn];
struct node{
    int to, nxt;
    int val;
}e[maxm];
int dep[maxn], ans;
int u, v, w;

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

inline bool bfs()
{
    queue <int> q;
    memset(dep, 0, sizeof dep);
    dep[s] = 1, q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int v, i = hd[u]; i; i = e[i].nxt)
        {
            if(e[i].val and !dep[v = e[i].to]) 
            {
                dep[v] = dep[u] + 1;
                q.push(v);
            }       
        }
    }
    if(dep[t]) return 1;
    return 0;
}

inline int dinic(int u, int in)
{
    if(u == t) return in;
    int out = 0;
    for(int i = hd[u]; i and in; i = e[i].nxt)
    {
        int v = e[i].to;
        if(dep[v] == dep[u] + 1 and e[i].val)
        {   
            int res = dinic(v, min(e[i].val, in));
            e[i].val -= res, e[i ^ 1].val += res;
            in -= res, out += res;
        }                                                                                                                
    }
    if(!out) dep[u] = 0;
    return out;
}

signed main()
{
    scanf("%d %d %d", &n, &f, &d);
    t = f + n + d + 1;
    rep(i, 1, f) add(s, i, 1);//源点连向食物 
    rep(i, 1, d) add(f + n + i, t, 1);//饮料连向汇点 
    rep(i, 1, n) add(f + i, t + i, 1);//每一个代表奶牛的店的拆分 
    rep(i, 1, n)
    {
        int tmp, ff, dd;
        scanf("%d %d", &ff, &dd);
        rep(j, 1, ff)
        {
            scanf("%d", &tmp);
            add(tmp, f + i, 1);//食物连向奶牛 
        }
        rep(j, 1, dd)
        {
            scanf("%d", &tmp);
            add(t + i/*注意是奶牛点的出点连向食物*/, f + n + tmp, 1);//奶牛连向食物 
        }
    }
    while(bfs()) ans += dinic(s, 1e16);//跑 Dinic 板子 
    printf("%d\n", ans);
    return 0;
}

——End——