[UVa10779]Collectors Problem

发布于 2017-12-16  23 次阅读



题目(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 
}
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;
}