比赛 |
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;
}