记录编号	367622	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-01-31 20:58:59	内存使用	0.54 MiB

//727
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <queue>


using namespace std;

const int nmax=10001;
const int INF=1<<29;


class edge
{
public:
	int from,to;
	int flow,cap;
};

vector<edge> edges;
vector<int > G[nmax];

int cur[nmax]={0};
int d[nmax]={0};
int vis[nmax]={0};
int sum,ans;
int n,m;
int s,t;

void AddEdge(int from,int to,int cap)
{
	edges.push_back((edge){from,to,0,cap});
	G[from].push_back(edges.size()-1);
	edges.push_back((edge){to,from,0,0});
	G[to].push_back(edges.size()-1);
}
bool GetInt(int &x)
{
	x=0;
	char ch=getchar();
	while(!(ch>='0'&&ch<='9'))
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x*=10;
		x+=ch-'0';
		ch=getchar();
	}
	if(int(ch)==13||int(ch)==10)
	{
		return 1;
	}
	return 0;
}

void PreDo()
{
	sum=0;
	ans=0;
	scanf("%d%d",&n,&m);
	s=0;
	t=n+m+1;
	int tmp;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&tmp);
		sum+=tmp;
		AddEdge(s,i,tmp);
		int qvq=0;
		while(1)
		{
			int tag=GetInt(qvq);
	//		printf("%d\n\n",qvq);
			AddEdge(i,qvq+n,INF);
			if(tag)
			{
				break;
			}
		}
//		Trans(i);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&tmp);
		AddEdge(i+n,t,tmp);
	}
}


bool BFS()
{	
	memset(vis,0,sizeof(vis));
	memset(d,0,sizeof(d));
	queue<int > Q;
	Q.push(s);
	vis[s]=1;
	d[s]=0;
	while(!Q.empty())
	{
		int tmpx=Q.front();
		Q.pop();
		for(int i=0;i<G[tmpx].size();i++)
		{
			edge &e=edges[G[tmpx][i]];
			if(vis[e.to]||e.cap<=e.flow)
			{
				continue;
			}
			d[e.to]=d[e.from]+1;
			vis[e.to]=1;
			Q.push(e.to);
		}
	}
	return vis[t];
}


int DFS(int tmpx,int a)
{
	if(tmpx==t||a==0)
	{
		return a;
	}
	int flow=0;
	int f=0;
	for(int &i=cur[tmpx];i<G[tmpx].size();i++)
	{
		edge &e=edges[G[tmpx][i]];
		if(d[e.from]+1==d[e.to])
		{
			f=DFS(e.to,min(a,e.cap-e.flow));
			if(f>0)
			{
				edges[G[tmpx][i]].flow+=f;
				edges[G[tmpx][i]^1].flow-=f;
				flow+=f;
				a-=f;
				if(a<=0)
				{
					return flow;
				}
			}
		}
	}
	return flow;
}

				
void Dinic()
{
	ans=0;
	while(BFS())
	{
		memset(cur,0,sizeof(cur));
		ans+=DFS(s,INF);
	}
}


void Col()
{
	for(int i=1;i<=n;i++)
	{
		if(vis[i])
		{
			printf("%d ",i);
		}
	}
	printf("\n");
	for(int j=n+1;j<=n+m;j++)
	{
		if(vis[j])
		{
			printf("%d ",j-n);
		}
	}
	printf("\n%d\n",sum-ans);
}


int main()
{
	freopen("shuttle.in","r",stdin);
	freopen("shuttle.out","w",stdout);
	PreDo();
	Dinic();
	Col();
	return 0;
}