【BZOJ】1711: [Usaco2007 Open]Dining吃饭

【算法】最大流

【题解】

S连向食物连向牛连向牛‘连向饮料连向T。

经典的一个元素依赖于两个元素的建图方式。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<queue>

using namespace std;

const int maxn=,inf=0x3f3f3f3f;

struct edge{int v,flow,from;}e[maxn];

int first[maxn],d[maxn],cur[maxn],tot=,S,T,n,A,B;

void insert(int u,int v,int w){//printf("%d %d\n",u,v);

    tot++;e[tot].v=v;e[tot].flow=w;e[tot].from=first[u];first[u]=tot;

    tot++;e[tot].v=u;e[tot].flow=;e[tot].from=first[v];first[v]=tot;

}

queue<int>q;

bool bfs(){

    memset(d,-,sizeof(d));

    d[S]=;q.push(S);

    while(!q.empty()){

        int x=q.front();q.pop();

        for(int i=first[x];i;i=e[i].from)

        if(e[i].flow&&d[e[i].v]==-){

            d[e[i].v]=d[x]+;

            q.push(e[i].v);

        }

    }

    return d[T]!=-;

}

int dinic(int x,int a){

    if(x==T||a==)return a;

    int flow=,f;

    for(int& i=cur[x];i;i=e[i].from)

    if(e[i].flow&&d[e[i].v]==d[x]+&&(f=dinic(e[i].v,min(e[i].flow,a)))>){

        e[i].flow-=f;

        e[i^].flow+=f;

        a-=f;

        flow+=f;

        if(a==)break;

    }

    return flow;

}

int main(){

    scanf("%d%d%d",&n,&A,&B);

    S=;T=A+n+n+B+;

    int u,v,w;

    for(int i=;i<=A;i++)insert(S,i,);

    for(int i=;i<=B;i++)insert(A+n+n+i,T,);

    for(int i=;i<=n;i++){

        scanf("%d%d",&u,&v);

        for(int j=;j<=u;j++){

            scanf("%d",&w);

            insert(w,A+i,);

        }

        for(int j=;j<=v;j++){

            scanf("%d",&w);

            insert(A+n+i,A+n+n+w,);

        }

        insert(A+i,A+n+i,);

    }

    int ans=;

    while(bfs()){

        for(int i=S;i<=T;i++)cur[i]=first[i];

        ans+=dinic(S,inf);

    }

    printf("%d",ans);

    return ;

}