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

using namespace std;

const int oo=1000000000;
const int MAXN=1111;
const int MAXM=111;
const int MAXP=MAXN+MAXM;
const int S=0;
const int T=MAXP-10;

struct edge
{
	int t,f;
	edge *p,*op;
}e[MAXN*MAXM*2],*v[MAXP];

double bg[MAXN],s[MAXM];
int lim[MAXN],i,j,es=-1,k,n,m,d[MAXP],vd[MAXP],ansflow,jo[MAXN][MAXM],tot[MAXN];

inline void addedge(int i,int j,int f)
{
	e[++es].t=j; e[es].f=f; e[es].p=v[i]; v[i]=e+es;
	e[++es].t=i; e[es].f=0; e[es].p=v[j]; v[j]=e+es;
	v[i]->op=v[j];
	v[j]->op=v[i];
}

int dfs(int u,int flow)
{
	int re=0,tmp;
	if (u==T) return flow;
	for (edge *x=v[u];x;x=x->p)
		if (x->f>0 && d[u]==d[x->t]+1)
		{
			tmp=dfs(x->t,min(flow-re,x->f));
			x->f-=tmp;
			x->op->f+=tmp;
			re+=tmp;
			if (re==flow) return re;
		}
	--vd[d[u]];
	if (vd[d[u]]==0) d[S]=T+1;
	vd[++d[u]]++;
	return re;
}

int main()
{
	freopen("cookies.in","r",stdin);
	freopen("cookies.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=m;i++)
	{
		scanf("%lf",&s[i]);
		for (j=1;j<=s[i];j++)
		{
			scanf("%d",&k);
			++tot[k];
			jo[k][tot[k]]=i;
		}
		addedge(i+n,T,1);
	}
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=tot[i];j++)
		{
			bg[i]+=1/s[jo[i][j]];
			addedge(i,jo[i][j]+n,1);
		}
		if ((int) bg[i]!=bg[i]) lim[i]=(int) bg[i]+1;
		else lim[i]=(int) bg[i];
		addedge(S,i,lim[i]);
	}
	memset(d,0,sizeof(d));
	memset(vd,0,sizeof(vd));
	vd[0]=T;
	while (d[S]<T)
		ansflow+=dfs(S,oo);
	if (ansflow<m)
	{
		printf("-1\n");
		return 0;
	}
	for (i=1;i<=m;i++)
		for (edge *x=v[n+i];x;x=x->p)
			if (x->f==1)
			{
				printf("%d\n",x->t);
				break;
			}
	return 0;
}