首页 > 代码库 > UVA-10779 Collectors Problem

UVA-10779 Collectors Problem

2024-09-23 16:01:33   217人阅读

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 3000using 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]=0;}bool bfs(){    while(!q.empty()) q.pop();    for(int i=1;i<=decc;i++) lev[i]=-1,cur[i]=front[i];    lev[src]=0;     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]]==-1&&cap[i]>0)            {                lev[to[i]]=lev[now]+1;                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=0,delta;    for(int &i=cur[now];i;i=nxt[i])    {        if(lev[to[i]]>lev[now]&&cap[i]>0)        {            delta=dinic(to[i],min(flow-rest,cap[i]));            if(delta)            {                cap[i]-=delta; cap[i^1]+=delta;                rest+=delta; if(rest==flow) break;            }        }    }    if(rest==flow) lev[now]=-1;    return rest;}int main(){    int T, n,m,x,k;    scanf("%d",&T);    for(int p=1;p<=T;p++)    {        tot=1;  src=http://www.mamicode.com/1;        memset(front,0,sizeof(front));        scanf("%d%d",&n,&m);        decc=n+m+1;        for(int i=1;i<=m;i++) add(n+i,decc,1);                scanf("%d",&k);        memset(sum,0,sizeof(sum));        while(k--)          {              scanf("%d",&x);              sum[x]++;         }        for(int i=1;i<=m;i++)            if(sum[i]) add(1,n+i,sum[i]);                for(int i=2;i<=n;i++)        {            memset(sum,0,sizeof(sum));            scanf("%d",&k);            while(k--)              {                 scanf("%d",&x);                  sum[x]++;             }            for(int j=1;j<=m;j++)             if(sum[j]>1) add(i,n+j,sum[j]-1);             else if(!sum[j])add(n+j,i,1);        }        int ans=0;        while(bfs()) ans+=dinic(src,5000);        printf("Case #%d: %d\n",p,ans);    }}

 

UVA-10779 Collectors Problem


联系
我们