[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);