首页 > 代码库 > UVA 10779 Collectors Problem[最大流]
UVA 10779 Collectors Problem[最大流]
from:neopenx
题目大意：Bob有一些贴纸，他可以和别人交换，他可以把自己独有的贴纸拿出去，也可以把重复的贴纸拿出去（有时候把独有的贴纸而不是重复的贴纸拿出去能换到更多贴纸）。
Bob的朋友也有一些贴纸，但是他们只会拿自己重复的贴纸和Bob换，而且换的是自己没有的贴纸。
求Bob最后最多能有多少种贴纸。
解题思路：
题目意思很明确了。就算把重复的贴纸拿出去也不一定最优，贪心就不用尝试了。
全局资源调配得使用网络流模型。
建图方式：
①S点(看作是Bob)->所有物品：连一条边，cap是Bob持有贴纸数量。
②：所有朋友->所有物品：如果这个人持有的该贴纸数量>=2,连一条边,cap是贴纸数量-1。（原因是这些人只会把重复的贴纸拿出去）。
③：所有物品->所有朋友：如果这个人没有改物品，连一条边，cap=1,。(原因是这些人会接受自己没有的贴纸）
④：所有物品->T点：连一条边，cap=1，统计物品的种类。
这样建图之后，所有物品可以看作Bob的总资产，这个总资产可以流进，也可以流出，在这基础上做一次最大流，就是结果了。
#include<cstdio>#include<cstring>#include<iostream>using namespace std;const int N=700;struct edge{int v,next,cap;}e[N<<1];int tot=1,head[N];int n,m,cas,Cas,S,T,dis[N],q[N],a[11][26];inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}inline void add(int x,int y,int z){ e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot; e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot;}inline bool bfs(){ for(int i=S;i<=T;i++) dis[i]=-1; int h=0,t=1;q[t]=S;dis[S]=0; while(h!=t){ int x=q[++h]; for(int i=head[x];i;i=e[i].next){ if(e[i].cap&&dis[e[i].v]==-1){ dis[e[i].v]=dis[x]+1; if(e[i].v==T) return 1; q[++t]=e[i].v; } } } return 0;}int dfs(int x,int f){ if(x==T) return f; int used=0,t; for(int i=head[x];i;i=e[i].next){ if(e[i].cap&&dis[e[i].v]==dis[x]+1){ t=dfs(e[i].v,min(e[i].cap,f)); e[i].cap-=t;e[i^1].cap+=t; used+=t;f-=t; if(!f) return used; } } if(!used) dis[x]=-1; return used;}inline int dinic(){ int res=0; while(bfs()) res+=dfs(S,2e9); return res;}int main(){ cas=read(); while(cas--){ tot=1;memset(a,0,sizeof a); memset(head,0,sizeof head); n=read();m=read(); for(int i=1,k,x;i<=n;i++){ k=read(); while(k--){ x=read(); a[i][x]++; } } S=0;T=n+m+1; for(int i=1;i<=m;i++){ add(S,i,a[1][i]); add(i,T,1); } for(int i=2;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]>=2) add(i+m,j,a[i][j]-1); if(!a[i][j]) add(j,i+m,1); } } printf("Case #%d: %d\n",++Cas,dinic()); } return 0;}
UVA 10779 Collectors Problem[最大流]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。