题解 P2891 【[USACO07OPEN]吃饭Dining】

· · 题解

最大流例题——[USACO07OPEN]吃饭Dining

这是一道比较经典的网络流的入门题。

相信和我一样的蒟蒻们看到这题的第一个想法都是超源连每种食品，食品连喜欢吃它的奶牛，奶牛连他喜欢吃的饮料，每种饮料连超汇，然后就无脑的套一波模板，闭着眼睛关上脑子抱着人有多大胆地有多大产的心态直接连样例都不过就交上去幻想着0msAC对不对！

作为经典例题哪有那么简（dou）单（bi）？

虽然我也是这么想的

但仔细想想就会发现——脑子怎么可能关上呢？对不对？

好吧，不开玩笑了，这题怎么可能那么简单就能过，因为文中有一个要求“每种食物或饮料只能供一头牛享用，且每头牛只享用一种食物和一种饮料”，怎么解决这个问题呢？这就需要一个网络流中的常用方法：拆点。

什么是拆点呢？其实就是把一个点拆成两个点（入点和出点），所有指向这个点的边都连向入点，而从这个点连出去的所有边的起点都在这个点的出点。就像下图一样：

拆点之后：

然后通过入点和出点间的容量（如图，为1）来限制经过这个点的流量，那么就只能有一种食物和一种饮料被这头牛吃。

这时，“每头牛只享用一种食物和一种饮料”的问题已解决，那么“每种食物或饮料只能供一头牛享用”怎么解决呢？

其实这个很简单，只要把超源连每种食物的每条边和每种饮料连超汇的每条边的容量设为1就行，这就保证了每种食物、饮料只能找到一个主人。

最后的图片如下（没把每个点都画出来，因为画不下那么大其实是因为我懒）：

最后直接跑最大流即可：

dinic算法：

#include<cstdio>
#include<queue>

#define N 500
#define M 200000
#define INF 0x7fffffff

using namespace std;

int n,f,d,head[N],to[M],c[M],nxt[M],num[N],minn,s,t,cnt,minflow,maxflow,tot;
 //用邻接表存边
queue<int>q;

void adde(int u,int v,int a){//建边
    cnt++;
    to[cnt]=v;
    c[cnt]=a;
    nxt[cnt]=head[u];
    head[u]=cnt;

    cnt++;
    to[cnt]=u;
    c[cnt]=0;
    nxt[cnt]=head[v];
    head[v]=cnt;
}

bool add_num() {//给每个点标号
    while(!q.empty()) {
        q.pop();
    }
    for(int i=s;i<=t+n;i++) {
        num[i]=-1;
    }
    num[s]=1;
    q.push(s);
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=nxt[i]) {
            if(c[i]&&num[to[i]]==-1) {
                num[to[i]]=num[now]+1;
                q.push(to[i]);
            }
        }
    }
    if(num[t]==-1) {//如果num[t]==-1，那么就说明到不了汇点，不能给汇点标号。
        return false;
    } else {
        return true;
    }
}

int dfs(int u,int s){
    if(u==t){
        return s;
    }
    for(int i=head[u];i;i=nxt[i]){
        if(c[i]&&num[u]+1==num[to[i]]&&(minflow=dfs(to[i],min(s,c[i])))){
            c[i]-=minflow;
            c[i^1]+=minflow;
            return minflow;
        }
    }
    return 0;
}

void dinic(){//dinic模板
    while(add_num()){
        while((minn=dfs(1,INF))){
            maxflow+=minn;
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&f,&d);
    cnt=1;
    s=1;
    t=1+f+n+d+1;
    for(int i=1;i<=f;i++){//超源连每种食品
        adde(s,1+i,1);
    }
    for(int i=1;i<=d;i++){//每种饮料连超汇
        adde(1+f+n+i,t,1);
    }
    for(int i=1;i<=n;i++){//入点连出点
        adde(1+f+i,1+f+n+d+1+i,1);
    }
    for(int i=1;i<=n;i++){
        int dn,fn;
        scanf("%d%d",&fn,&dn);
        for(int q=1;q<=fn;q++){//食品连喜欢吃它的奶牛
            int fi;
            scanf("%d",&fi);
            adde(1+fi,1+f+i,1);
        }
        for(int q=1;q<=dn;q++){//奶牛连他喜欢吃的饮料
            int di;
            scanf("%d",&di);
            adde(1+f+n+d+1+i,1+f+n+di,1);
        }
    }
    dinic();
    printf("%d\n",maxflow);//输出
    return 0;
}

注：EK朴素算法也可以过得去。 如果是入门最大流也可以用邻接矩阵存边。