学步园

题目链接:   poj 3281

题目大意:   有N头奶牛，A种食物和B种饮料，每头奶牛都有自己喜欢的食物和饮料

                  问有最多有多少头奶牛既可以得到自己喜欢的食物又可以得到喜欢的饮料

解题思路:   开始没有把奶牛分成两个点，这样会导致几种食物流入同一头奶牛

                  正确的构图:

                  1.建立超级源点，源点分别指向A种不同的食物，容量为1

                  2.建立超级汇点，B种不同的饮料分别指向汇点，容量为1

                  3.每头奶牛分成两个点T和T''，T指向T''，容量为1

                  4.把T奶牛喜欢的食物指向T，容量为1，再把T''指向喜欢的饮料

                  PS:用邻接表时要注意反向边也要加入，因为需要不断增广直到最优解

代码:

//19:37--->20:53
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 105
#define INF 0x3f3f3f3f
int S,E,visit[MAX<<2],flag[MAX<<2][MAX<<2],Map[MAX<<2][MAX<<2];
struct snode{
    int c,to,next;
}Edge[MAX*MAX*MAX];

int listb[MAX*MAX*MAX],pre[MAX<<2],Index;

int Min(int a,int b)
{
    return(a<b?a:b);
}

void Add_edge(int a,int b,int c)
{
    Edge[Index].to=b,Edge[Index].c=c;
    Edge[Index].next=pre[a];
    pre[a]=Index++;
}


bool BFS()
{
    int i,e,s,v,vv;
    e=s=0;
    memset(visit,0,sizeof(visit));
    memset(flag,0,sizeof(flag));
    listb[s++]=S;
    visit[S]=1;
    while(s!=e)
    {
        v=listb[e++];
        if(v==E)
        {
            return true;
        }
        for(i=pre[v];i!=-1;i=Edge[i].next)
        {
            vv=Edge[i].to;
            if(Map[v][vv]&&!visit[vv])
            {
                flag[v][vv]=1;
                listb[s++]=vv;
                visit[vv]=1;
            }
        }
    }
    return false;
}

int DFS(int v,int sum)
{
    int s,t,i,vv;
    if(v==E||sum==0)
        return sum;
    s=sum;
    for(i=pre[v];i!=-1;i=Edge[i].next)
    {
        vv=Edge[i].to;
        if(flag[v][vv])
        {
            t=DFS(vv,Min(sum,Map[v][vv]));
            Map[v][vv]-=t;
            Map[vv][v]+=t;
            sum-=t;
        }
    }
    return s-sum;
}

int Solve()   //Dinic
{
    int sum=0,t;
    while(BFS())
    {
        t=DFS(S,INF);
        sum+=t;
    }
    return sum;
}

int main()
{
    int n,A,B,i,j,a,b,c;
    while(scanf("%d%d%d",&n,&A,&B)!=EOF)
    {
        S=0,E=A+B+n+n+1;
        Index=0;
        memset(Map,0,sizeof(Map));
        memset(pre,-1,sizeof(pre));
        for(i=1;i<=A;i++)   //左边
        {
            a=S,b=i,c=1;
            Add_edge(a,b,c);
            Add_edge(b,a,-c);
            Map[a][b]=c;
        }
        for(i=1;i<=B;i++)   //右边
        {
            a=A+n+n+i,b=E,c=1;
            Add_edge(a,b,c);
            Add_edge(b,a,-c);
            Map[a][b]=c;
        }
        for(i=1;i<=n;i++)   //最中间
        {
            a=A+i,b=A+n+i,c=1;
            Add_edge(a,b,c);
            Add_edge(b,a,-c);
            Map[a][b]=c;
        }
        for(i=1;i<=n;i++)    //中左，中右
        {
            int t1,t2,t3,t4;
            scanf("%d%d",&t1,&t2);
            for(j=1;j<=t1;j++)
            {
                scanf("%d",&t3);
                a=t3,b=A+i,c=1;
                Add_edge(a,b,c);
                Add_edge(b,a,-c);
                Map[a][b]=c;
            }
            for(j=1;j<=t2;j++)
            {
                scanf("%d",&t4);
                a=i+A+n,b=A+n+n+t4,c=1;
                Add_edge(a,b,c);
                Add_edge(b,a,-c);
                Map[a][b]=c;
            }
        }
        printf("%d\n",Solve());
    }
    return 0;
}