UVA-10779 Collectors Problem

https://vjudge.net/problem/UVA-10779

题意：n个人，m种贴纸，每个人开始有一些贴纸

第一个人可以跟任何人交换任何贴纸

其余人只能用重复的贴纸 跟第一个人交换他们没有的贴纸

问第一个人最后最多有多少种贴纸

关键点：其余人只能从第一个人手中得到一张他们没有的贴纸，每种贴纸 最多给第一个人 这种贴纸数-1张

建图：

第一个人向它有的贴纸连边，流量为他有的贴纸数量

每一种贴纸向汇点连流量为1的边

其余人，如果没有贴纸i，由i向这个人连一条流量为1的边，

如果贴纸i数量>1，由这个人向i连一条流量为数量-1的边

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 40

#define M 3000

using namespace std;

int sum[N];

int front[N],to[M],nxt[M],tot;

int cap[M],lev[N],cur[N];

int decc,src;

queue<int>q;

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=w;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=;

}

bool bfs()

{

    while(!q.empty()) q.pop();

    for(int i=;i<=decc;i++) lev[i]=-,cur[i]=front[i];

    lev[src]=;

    q.push(src);

    int now;

    while(!q.empty())

    {

        now=q.front(); q.pop();

        for(int i=front[now];i;i=nxt[i])

        {

            if(lev[to[i]]==-&&cap[i]>)

            {

                lev[to[i]]=lev[now]+;

                if(to[i]==decc) return true;

                q.push(to[i]);

            }

        }

    }

    return false;

}

int dinic(int now,int flow)

{

    if(now==decc) return flow;

    int rest=,delta;

    for(int &i=cur[now];i;i=nxt[i])

    {

        if(lev[to[i]]>lev[now]&&cap[i]>)

        {

            delta=dinic(to[i],min(flow-rest,cap[i]));

            if(delta)

            {

                cap[i]-=delta; cap[i^]+=delta;

                rest+=delta; if(rest==flow) break;

            }

        }

    }

    if(rest==flow) lev[now]=-;

    return rest;

}

int main()

{

    int T, n,m,x,k;

    scanf("%d",&T);

    for(int p=;p<=T;p++)

    {

        tot=;  src=;

        memset(front,,sizeof(front));

        scanf("%d%d",&n,&m);

        decc=n+m+;

        for(int i=;i<=m;i++) add(n+i,decc,);

        scanf("%d",&k);

        memset(sum,,sizeof(sum));

        while(k--)

        {

            scanf("%d",&x);

            sum[x]++;

        }

        for(int i=;i<=m;i++)

          if(sum[i]) add(,n+i,sum[i]);

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

        {

            memset(sum,,sizeof(sum));

            scanf("%d",&k);

            while(k--)

            {

                scanf("%d",&x);

                sum[x]++;

            }

            for(int j=;j<=m;j++)

             if(sum[j]>) add(i,n+j,sum[j]-);

             else if(!sum[j])add(n+j,i,);

        }

        int ans=;

        while(bfs()) ans+=dinic(src,);

        printf("Case #%d: %d\n",p,ans);

    }

}