比赛 20110412 评测结果 WWWWWWWWWW
题目名称 请客 最终得分 0
用户昵称 .Xmz 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-04-12 10:56:45
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

const int maxn=1111;

struct edge
{
	int t,c;
	edge *next,*op;
}E[500001],*V[maxn];
int eh,n,m,S,T,pn;
inline void addedge(int a,int b,int c)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t=b;  V[a]->c=c;
	E[++eh].next=V[b];  V[b]=E+eh;  V[b]->t=a;  V[b]->c=0;
	V[a]->op=V[b];  V[b]->op=V[a];
}

int num[maxn];
double lim[maxn];

void init()
{
	scanf("%d%d",&n,&m);
	S=0,T=n+m+1;
	int t;
	for (int i=1;i<=m;i++)
	{
		scanf("%d",num+i);
		for (int j=1;j<=num[i];j++)
		{
			scanf("%d",&t);
			lim[t]+=1/(double)num[i];
			addedge(i,m+t,1);
		}
		addedge(S,i,1);
	}
	for (int i=1;i<=n;i++)
		addedge(i+m,T,ceil(lim[i]-1e-8));
	pn=n+m+2;
}

int d[maxn],vd[maxn];

int aug(int u,int flow)
{
	int now=0;
	if (u==T) return flow;
	for (edge *e=V[u];e;e=e->next)
	if (e->c && d[e->t]+1==d[u])
	{
		int t=aug(e->t,min(flow-now,e->c));
		if (t)
		{
			e->c -= t;
			e->op->c += t;
			now += t;
			if (now==flow) return now;
		}
	}
	if (d[S]>=pn) return now;
	if (--vd[d[u]]==0) d[S]=pn;
	++vd[++d[u]];
	return now;
}

void solve()
{
	int flow=0;
	vd[0]=pn;
	while (d[S]<pn)
	{
		flow+=aug(S,10000);
	}
	
	if (flow==m)
	{
		for (int u=1;u<=m;u++)
		for (edge *e=V[u];e;e=e->next)
		if (e->t!=S && e->c==0)
		printf("%d\n",e->t-m);
	}
	else printf("-1\n");
}

int main()
{
	freopen("cookie.in","r",stdin);
	freopen("cookie.out","w",stdout);
	init();
	solve();
	return 0;
}