记录编号	91156	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	rpCardinal	是否通过	通过
代码语言	C++	运行时间	0.062 s
提交时间	2014-03-12 13:47:26	内存使用	0.44 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define S n+m+1
#define T n+m+2
#define N n+m+2
#define INF 10000000
using namespace std;

int n,m,i,x,ans,g[250][250],h[250];
queue <int> q;
char ch;

int dfs(int x,int sum)
{
	int t,y,last=sum;
	if (x==T) return sum;
	for (y=1;y<=N&&sum;y++)
		if (g[x][y]>0&&h[y]==h[x]+1)
		{
			t=dfs(y,min(sum,g[x][y]));
			g[x][y]-=t; g[y][x]+=t; sum-=t;
		}
	return last-sum;
}

bool bfs()
{
	int x,y;
	memset(h,-1,sizeof(h));
	h[S]=0; q.push(S);
	while (!q.empty())
	{
		x=q.front(); q.pop();
		for (y=1;y<=N;y++)
			if (g[x][y]>0&&h[y]==-1)
			{
				h[y]=h[x]+1;
				q.push(y);
			}
	}
	return h[T]>=0;
}

int dinic()
{
	int ret=0;
	while (bfs()) ret+=dfs(S,INF);
	return ret;
}

int main()
{
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	scanf("%d%d",&m,&n);
	for (i=1;i<=m;i++)
	{
		scanf("%d",&g[S][i]);
		ans+=g[S][i];
		while (true)
		{
			while ((ch=getchar())==' ') ;
			ungetc(ch,stdin);
			if (ch=='\n'||ch=='\r') break;
			scanf("%d",&x);
			g[i][m+x]=INF;
		}
	}
	for (i=1;i<=n;i++) scanf("%d",&g[m+i][T]);
	ans-=dinic();
	for (i=1;i<=m;i++)
		if (h[i]>=0)
			printf("%d ",i);
	putchar('\n');
	for (i=1;i<=n;i++)
		if (h[m+i]>=0)
			printf("%d ",i);
	putchar('\n');
	printf("%d\n",ans);
	fclose(stdin); fclose(stdout);
	return 0;
}