首页 > 代码库 > UVA-10779 Collectors Problem
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 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。