记录编号	149089	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-02-18 16:46:23	内存使用	0.58 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
const int inf=0x3f3f3f3f;
int n,m,en,ans,len=1,g[205],d[205],q[205],p[205];
int to[25000],cap[25000],next[25000];
void add(int x,int y,int z){
	to[++len]=y,next[len]=g[x],cap[len]=z,g[x]=len;
	to[++len]=x,next[len]=g[y],cap[len]=0,g[y]=len;
}
bool bfs(){
	int l=1,r=1;
	memset(d,0,sizeof d),d[0]=1,q[1]=0;
	while(l<=r){
		int x=q[l++];
		for(int i=g[x];i;i=next[i])
			if(!d[to[i]]&&cap[i]) 
				q[++r]=to[i],d[to[i]]=d[x]+1; 
	}
	return d[en];
}
int dfs(int x,int y){
	if(x==en||!y) return y;int flow=0;
	for(int &i=p[x];i;i=next[i]){
		if(!cap[i]||d[to[i]]!=d[x]+1) continue;
		int f=dfs(to[i],std::min(y,cap[i]));
		flow+=f,y-=f,cap[i]-=f,cap[i^1]+=f;
		if(!y) break;
	}
	return flow;
}
int main(){
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	scanf("%d%d",&n,&m),en=n+m+1;
	for(int x,y,i=1;i<=n;i++){
		scanf("%d",&x),ans+=x,add(0,i,x);
		while(scanf("%d%c",&x,&y)){
			add(i,x+n,inf);
			if(y=='\r') break;
		}
	}
	for(int x,i=1;i<=m;i++) scanf("%d",&x),add(i+n,en,x);
	while(bfs()){
		memcpy(p,g,sizeof p);
		ans-=dfs(0,inf);
	}
	for(int i=1;i<=n;i++)
		if(d[i]) printf("%d ",i);
	putchar('\n');
	for(int i=1;i<=m;i++)
		if(d[i+n]) printf("%d ",i);
	printf("\n%d",ans);
}