题目（vjudge）
这里没有题目大意，自己翻译去（哼）。
来说说这题吧。
首先，这题明显就是个网络流（看数据范围），
然后就来考虑怎么建模。
网络流的建模都很迷的（至少我这么认为），但要是建出来了会发现很好理解也很巧妙。
而这个题......说老实话算网络流的入门了。
首先，来一个超级源点S和超级汇点T，用m个点表示m种糖纸，n-1个点表示除Bob外的n-1个人。
然后，因为是求最多种类数，那么这n-1个点就分别向T连一条弧，容量为1.
（废话，只要Bob手上有这种糖纸答案就+1）
然后，S向这m个点各连一条弧，容量为最初Bob有这种糖纸多少张，
最后就是最关键的了！
根据题意，Bob与朋友交换糖纸时，朋友只收他没有的糖纸，
换句话说，Bob最多只能给他一张他没有的糖纸，多了的朋友就不要了。
于是，建模就很清晰了：
如果第i个朋友没有第j种糖纸，那么就从j->i连一条弧，容量为1，
然后朋友还会给你糖纸啊！当然是给你他手上原来有的啊！
所以，若第i个朋友有第j种糖纸至少两张（1.你刚给他的不算 2.他要留一张），那就从i->j连一条弧，容量为这个朋友有第j张糖纸的张数-1.
最后，跑一遍最大流，完毕！
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <climits>
#define ll long long
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
const int inf=0x3f3f3f3f;
using namespace std;
template <class _E> inline void read(_E &e)
{
e=0;bool ck=0;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
while(ch<='9'&&ch>='0'){e=e*10+ch-'0';ch=getchar();}
if(ck)e=-e;
}
int n,m;
int s,t;
struct edge{
int vk;
int flow;
int next;
}e[33005];
int k,head[55];
int a[55];
int d[55];
int c[15][30];
queue <int> q;
void ad(int u,int v,int w)
{
e[++k].vk=v;
e[k].flow=w;
e[k].next=head[u];
head[u]=k;
}
inline bool bfs()
{
while (!q.empty()) q.pop();
memset(d,-1,sizeof d);
d[s]=1;
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].vk;
if (e[i].flow && d[v]==-1)
{
d[v]=d[u]+1;
q.push(v);
}
}
}
return d[t]!=-1;
}
int dfs(int u,int flow)
{
if (u==t || !flow) return flow;
int ret=0,res;
for (int i=head[u];i;i=e[i].next)
{
int v=e[i].vk;
if (d[v]>d[u] && e[i].flow)
{
res=dfs(v,min(e[i].flow,flow));
if (res)
{
e[i].flow-=res;
e[i^1].flow+=res;
ret+=res;
flow-=res;
if (!flow) return ret;
}
}
}
return ret;
}
inline int dinic()
{
int flow=0;
while (bfs()) flow+=dfs(s,inf);
return flow;
}
void printans(int noo,int answer)
{
printf("Case #%d: %d\n",noo,answer);
}
int main()
{
int TT,kase=0;
s=0,t=50;
read(TT);
while (TT--)
{
k=0,memset(head,0,sizeof head);
memset(a,0,sizeof a),memset(d,0,sizeof d);
memset(c,0,sizeof c);
read(n),read(m);
for (int i=1;i<=n;++i)
{
int num;
read(num);
for (int j=1;j<=num;++j)
{
int color;
read(color);
++c[i][color];
}
}
for (int i=1;i<=m;++i)
{
int cap=c[1][i];
ad(s,i,cap),ad(i,s,0);
ad(i,t,1),ad(t,i,0);
}
for (int i=2;i<=n;++i)
{
int vk=i+2*n;
for (int j=1;j<=m;++j)
{
int cap=c[i][j];
if (!cap) ad(j,vk,1),ad(vk,j,0);
else if (cap>1)
{
ad(vk,j,cap-1),ad(j,vk,0);
}
}
}
int ans=dinic();
printans(++kase,ans);
}
return 0;
}
Comments NOTHING