BZOJ1711 [Usaco2007 Open]Dining吃饭

题意：

有\(n\)头牛，\(F\)种食物、\(D\)种饮料各一种，每头牛有一个喜欢的食物、饮料集合而且它只能吃各一种，问如何分配使都吃到和喝到自己喜欢的东西的牛数最多。

知识点：

最大流

解法：

设点\(A_i\)和\(B_i\)分别表示食物和饮料，\(S\)点连\(A_i\)，\(B_i\)连\(T\)，都连\(1\)边，表示有这么的食物和饮料各一种。

然后设点\(C_i\)和\(D_i\)表示一头牛，\(C_i\)连\(D_i\)一条\(1\)边表示一头牛满足的话算且只算一次。

最后对于每头牛，喜欢的食物连向\(C_i\)，\(D_i\)连向喜欢的饮料。

最大流即为答案。

代码：

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;

const int maxn=210,maxm=40600,inf=0x7fffffff;
int n,F,D,S,T,tot,head[maxn<<1],dis[maxn<<1],cur[maxn<<1];
struct node
{
    int nxt,to,w;
}edge[maxm];
queue<int>q;

int read()
{
    int x=0;
    char c=getchar();
    while (c<48||c>57)
        c=getchar();
    while (c>=48&&c<=57)
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

void add(int u,int v,int w)
{
    edge[++tot]=(node){head[u],v,w};
    head[u]=tot;
}

void link(int u,int v,int w)
{
    add(u,v,w);
    add(v,u,0);
}

int dfs(int u,int flow)
{
    if (u==T)
        return flow;
    int i,res=flow,v,tmp;
    for (i=head[u];i;i=edge[i].nxt)
    {
        v=edge[i].to;
        if (dis[v]==dis[u]+1&&edge[i].w>0)
        {
            tmp=dfs(v,min(edge[i].w,res));
            edge[i].w-=tmp;
            edge[i^1].w+=tmp;
            res-=tmp;
            if (!res)
                break;
        }
    }
    return flow-res;
}

bool bfs()
{
    while (!q.empty())
        q.pop();
    memset(dis,0,sizeof(dis));
    int i,u,v;
    q.push(S);
    dis[S]=1;
    while (!q.empty())
    {
        u=q.front();
        q.pop();
        for (i=head[u];i;i=edge[i].nxt)
        {
            v=edge[i].to;
            if (!dis[v]&&edge[i].w>0)
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[T];
}

int dinic()
{
    int ans=0,i,tmp;
    while (bfs())
    {
        for (i=1;i<=T;i++)
            cur[i]=head[i];
        tmp=dfs(S,inf);
        if (!tmp)
            break;
        ans+=tmp;
    }
    return ans;
}

int main()
{
    int i,j,k;
    tot=1;
    n=read(),F=read(),D=read();
    S=2*n+F+D+1,T=S+1;
    for (i=1;i<=F;i++)
        link(S,i,1);
    for (i=1;i<=D;i++)
        link(i+F,T,1);
    for (i=1;i<=n;i++)
    {
        link(F+D+i,F+D+n+i,1);
        j=read(),k=read();
        while (j--)
            link(read(),F+D+i,1);
        while (k--)
            link(F+D+n+i,F+read(),1);
    }
    printf("%d\n",dinic());
    return 0;
}

BZOJ1711 [Usaco2007 Open]Dining吃饭

原文：https://www.cnblogs.com/Ronald-MOK1426/p/12300220.html