题目链接：https://vjudge.net/problem/UVA-10779（VJudge）
Bob有一些贴纸，他可以和别人交换，他可以把自己独有的贴纸拿出去，也可以把重复的贴纸拿出去（有时候把独有的贴纸拿出去能换到更多贴纸[比那重复的贴纸出去]）。Bob的朋友也有一些贴纸，但是他们只会拿自己重复的贴纸和Bob换，而且换的是自己没有的贴纸。求Bob最后最多能有多少种贴纸。
分析： 题目意思很明确了。就算把重复的贴纸拿出去也不一定最优，贪心就不用尝试了。 全局资源调配得使用网络流模型。 建图方式： ①S点(看作是Bob)->所有物品：连一条边，cap是Bob持有贴纸数量。 ②：所有朋友->所有物品：如果这个人持有的该贴纸数量>=2,连一条边,cap是贴纸数量-1。（原因是这些人只会把重复的贴纸拿出去）。 ③：所有物品->所有朋友：如果这个人没有改物品，连一条边，cap=1,。(原因是这些人会接受自己没有的贴纸） ④：所有物品->T点：连一条边，cap=1因为是统计邮票的种类而不是邮票的数目。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #include<cstdlib> #include<queue> using namespace std; #define LL long long #define maxn 100 #define maxm 500 #define INF 100000000 int n,m,S,T,tot=1; int rec[35],head[maxn],dep[maxn]; queue<int> q; struct Edge{ int next,to,value; }e[maxm]; void Prepare(){ tot=1; memset(head,0,sizeof head ); } void Add_Edge(int u,int v,int w){ e[++tot].to=v; e[tot].value=w; e[tot].next=head[u]; head[u]=tot; e[++tot].to=u; e[tot].value=0; e[tot].next=head[v]; head[v]=tot; } void InPut(){ scanf("%d%d",&n,&m); S=0;T=n+m+10; int x,y; memset(rec,0,sizeof rec ); scanf("%d",&x); for(int i=0;i<x;i++){ scanf("%d",&y);rec[y]++; } for(int i=1;i<=m;i++) if(rec[i]) Add_Edge(S,i,rec[i]); for(int i=1;i<n;i++){ scanf("%d",&x); memset(rec,0,sizeof rec ); for(int j=0;j<x;j++){ scanf("%d",&y);rec[y]++; } for(int j=1;j<=m;j++){ if(rec[j]>1) Add_Edge(i+m,j,rec[j]-1); else if(rec[j]==0) Add_Edge(j,i+m,1); } } for(int i=1;i<=m;i++) Add_Edge(i,T,1); } bool BFS(){ memset(dep,-1,sizeof dep ); dep[S]=0;q.push(S); while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(dep[v] == -1&&e[i].value){ dep[v]=dep[u]+1;q.push(v); } } } if(dep[T] == -1) return false; else return true; } int DFS(int u,int flow){ if(u==T) return flow; int ret=0; for(int i=head[u];i;i=e[i].next){ int v=e[i].to; if(dep[v]==dep[u]+1&&e[i].value){ int x=DFS(v,min(e[i].value,flow-ret)); ret+=x;flow-=x; e[i].value-=x;e[i^1].value+=x; } } return ret; } int Dinic(){ int ans=0; while(BFS()) ans+=DFS(S,INF); return ans; } int main(){ int T,Case=1; scanf("%d",&T); while(T--){ Prepare(); InPut(); printf("Case #%d: %d\n",Case++,Dinic()); } return 0; } /* 2 2 5 6 1 1 1 1 1 1 3 1 2 2 3 5 4 1 2 1 1 3 2 2 2 5 1 3 4 4 3 */