记录编号	147259	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-01-27 17:27:53	内存使用	0.35 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,m,i,p,zj1,zj2,zj3,ans,ST,SD;
const int INF=1e9;

int que[250]={0},que_head=1,que_tail=0;
void PUSH(int x){que[0]++;if((++que_tail)==250)que_tail=1;que[que_tail]=x;}
int GET(){int x=que[que_head];que[0]--;if((++que_head)==250)que_head=1;return x;}

int to[3000]={0},ne[3000]={0},head[250]={0},w[3000]={0},sj=1;
void Addedge(int u,int v,int z)
{
	to[++sj]=v,ne[sj]=head[u],head[u]=sj,w[sj]=z;
	to[++sj]=u,ne[sj]=head[v],head[v]=sj,w[sj]=0;
}

int lv[250]={0},cnt[250]={0};
void init()
{
	scanf("%d%d",&m,&n);
	char ch;ST=n+m+1,SD=ST+1;
	for(i=1;i<=m;i++)
	{
		scanf("%d",&zj1);ans+=zj1;
		Addedge(ST,i,zj1);
		while((ch=getchar())!='\r')
		{
			scanf("%d",&zj1);
			Addedge(i,m+zj1,INF);
		}
	}
	for(i=1;i<=n;i++)
	{
		scanf("%d",&zj1);
		Addedge(i+m,SD,zj1);
	}
	PUSH(SD);
	while(que[0])
	{
		zj1=GET();
		for(i=head[zj1];i;i=ne[i])
		if(w[i^1]&&!lv[to[i]])
		{
			cnt[lv[to[i]]=lv[zj1]+1]++;
			PUSH(to[i]);
		}
	}
	cnt[lv[SD]]--,cnt[lv[SD]=0]=1;
}

int pre[250]={0},cur[250]={0};
void isap()
{
	for(i=1;i<=SD;i++)cur[i]=head[i];
	int U=ST;pre[U]=U,zj1=INF;bool flag;
	while(lv[U]<SD)
	{
	    flag=0;
	    for(i=cur[U];i;i=ne[i])
	    {
			if(w[i]&&lv[to[i]]==lv[U]-1)
			{
				flag=1,pre[to[i]]=U,U=to[i];
				if(zj1>w[i])zj1=w[i];
				if(U==SD)
				{
					while(U!=ST)
					U=pre[U],w[cur[U]]-=zj1,w[cur[U]^1]+=zj1;
					ans-=zj1,zj1=INF;
				}
				break;
			}
			cur[U]=ne[i];
	    }
	    if(flag)continue;
	    if(!(--cnt[lv[U]]))break;
	    zj2=SD;
	    for(i=head[U];i;i=ne[i])
	    if(w[i]&&lv[to[i]]<zj2)zj2=lv[to[i]],cur[U]=i;
	    cnt[lv[U]=zj2+1]++,U=pre[U];
	}
}

bool vis[250]={0};
void DFS(int now)
{
	vis[now]=1;
	for(int j=head[now];j;j=ne[j])
    if(w[j]&&!vis[to[j]])DFS(to[j]);
}

void END_()
{
	DFS(ST);
	for(i=1;i<=m;i++)if(vis[i])printf("%d ",i);
	printf("\n");
	for(i=1;i<=n;i++)if(vis[i+m])printf("%d ",i);
	printf("\n");
	printf("%d\n",ans);
}
int main()
{
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	init();
	isap();
	END_();
	//while(1);
	return 0;
}