BZOJ1711: [Usaco2007 Open]Dining吃饭【网络流】

1711: [Usaco2007 Open]Dining吃饭

【题目描述】

传送门

【题解】

对于每头奶拆成两个点建边,一个和食物连一个和饮料连(注意方向)。

代码如下

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=4*105,MAXE=105*105+105*2;
int n,F,D,S,T,Dep[MAXN],Hed[MAXN];
struct Edge{
    int tot,lnk[MAXN],son[MAXE<<1],nxt[MAXE<<1],C[MAXE<<1];
    void clean(){memset(lnk,-1,sizeof(lnk));tot=-1;}
    void Add_E(int x,int y,int f){son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;C[tot]=f;}
    void Add(int x,int y,int f){Add_E(x,y,f),Add_E(y,x,0);}
}E;
queue<int> que;
bool BFS(int x){
    memset(Dep,0,sizeof(Dep));
    while(!que.empty()) que.pop();
    que.push(x);Dep[x]=1;
    while(!que.empty()){
        x=que.front();que.pop();
        for(int j=E.lnk[x];j^-1;j=E.nxt[j])
        if(!Dep[E.son[j]]&&E.C[j]>0) Dep[E.son[j]]=Dep[x]+1,que.push(E.son[j]);
    }
    return Dep[T];
}
int DFS(int x,int flow){
    if(x==T) return flow;
    int Now=0;
    for(int j=Hed[x];j^-1;Hed[x]=j=E.nxt[j])
    if(Dep[E.son[j]]==Dep[x]+1&&E.C[j]>0){
        int y=DFS(E.son[j],min(flow,E.C[j]));
        if(y>0){E.C[j]-=y;E.C[j^1]+=y;Now+=y,flow-=y;if(!flow) break;}
    }
    return Now;
}
int Dinic(){
    int Ans=0;
    while(BFS(S)){
        for(int i=1;i<=T;i++) Hed[i]=E.lnk[i];
        Ans+=DFS(S,1e9);
    }
    return Ans;
}
int main(){
    scanf("%d%d%d",&n,&F,&D);E.clean();T=(S=F+D+2*n+1)+1;
    for(int i=1;i<=F;i++) E.Add(S,i,1);
    for(int i=1;i<=D;i++) E.Add(F+n*2+i,T,1);
    for(int i=1;i<=n;i++){
        int K1,K2;scanf("%d%d",&K1,&K2);
        E.Add(F+i,F+n+i,1);
        for(int j=1,x;j<=K1;j++) scanf("%d",&x),E.Add(x,F+i,1);
        for(int j=1,x;j<=K2;j++) scanf("%d",&x),E.Add(F+n+i,F+n*2+x,1);
    }
    printf("%d\n",Dinic());
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部