[UVa10779]Collectors Problem（最大流）

2019-11-08 02:33:51

字体：大中小

来源：转载

供稿：网友

题目描述

传送门

题意：有T(T≤20)组数据。Bob在与他的n−1(2≤n≤10)个同伴交换糖纸，一共有m(5≤m≤25)种糖纸。Bob希望能和同伴交换使得手上的糖纸数尽量多。他的同伴只会用手上的重复的交换手上没有的，并且他的同伴们之间不会产生交换。求出Bob能拥有的最大糖纸种数。

题解

因为同伴只愿意用多余的交换没有的，所以Bob拿一种糖纸只能与一个同伴交换一次建立s,t，两排点xi,yi，xi表示第i种糖纸，yi表示除Bob外的第i个同伴 s->xi，容量为Bob拥有的第i种糖纸数量，xi->t，容量为1 对于一个同伴i，如果他没有第j种糖纸，那么xj->yi，容量为1 如果他有第j种糖纸，那么yi->xj，容量为他有的糖纸数量-1

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>#include<queue>using namespace std;#define N 50#define E 2005#define inf 2000000000int T,Case,n,m,x,y,s,t,maxflow;int cnt[N][N];int tot,point[N],nxt[E],v[E],remain[E];int deep[N],cur[N];queue <int> q;void clear(){ n=m=x=y=s=t=maxflow=0; memset(cnt,0,sizeof(cnt)); tot=-1;memset(point,-1,sizeof(point));}void addedge(int x,int y,int cap){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=cap; ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=0;}bool bfs(int s,int t){ for (int i=1;i<=t;++i) deep[i]=t; deep[s]=0; for (int i=1;i<=t;++i) cur[i]=point[i]; while (!q.empty()) q.pop(); q.push(s); while (!q.empty()) { int now=q.front();q.pop(); for (int i=point[now];i!=-1;i=nxt[i]) if (deep[v[i]]==t&&remain[i]) { deep[v[i]]=deep[now]+1; q.push(v[i]); } } return deep[t]<t;}int dfs(int now,int t,int limit){ if (now==t||!limit) return limit; int flow=0,f; for (int i=cur[now];i!=-1;i=nxt[i]) { cur[now]=i; if (deep[v[i]]==deep[now]+1&&(f=dfs(v[i],t,min(remain[i],limit)))) { flow+=f; limit-=f; remain[i]-=f; remain[i^1]+=f; if (!limit) break; } } return flow;}void dinic(int s,int t){ while (bfs(s,t)) maxflow+=dfs(s,t,inf);}int main(){ scanf("%d",&T); while (T--) { clear(); scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) { scanf("%d",&x); while (x--) scanf("%d",&y),++cnt[i][y]; } s=n+m,t=s+1; for (int i=1;i<=m;++i) { if (cnt[1][i]) addedge(s,i,cnt[1][i]); addedge(i,t,1); } for (int i=1;i<=m;++i) for (int j=2;j<=n;++j) { if (!cnt[j][i]) addedge(i,m+j-1,1); if (cnt[j][i]>1) addedge(m+j-1,i,cnt[j][i]-1); } dinic(s,t); PRintf("Case #%d: %d/n",++Case,maxflow); }}

上一篇：A strange lift HDU - 1548

下一篇：【LeetCode】451. Sort Characters By Frequency【M】【68】

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注