记录编号	149153	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2015-02-20 00:20:41	内存使用	0.43 MiB

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <queue>
using namespace std;
#ifdef DEBUG
FILE *in = fopen("test.txt", "r");
#define out stdout
#else
FILE *in = fopen("shuttle.in", "r");
FILE *out = fopen("shuttle.out", "w");
#endif
#define getc() fgetc(in)
template<class T>inline bool getd(T &x){
	int ch = getc();bool neg = false;
	while(ch != EOF && ch != '-' && !isdigit(ch))ch = getc();
	if(ch == EOF)return false;
	if(ch == '-')neg = true, ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
	return true;
}
/******************************************************************/
const int maxn = 205, maxe = 10205, INF = 0x3f3f3f3f;
struct Edge{
	int u, v, c;
	inline void set(int fr, int to, int vol){u = fr, v = to, c = vol;}
}E[maxe], *Eend = E, *from[maxn];

int M, N, S, T, Ans, Sum, h[maxn];

vector<Edge*> adj[maxn];

inline void AddE(int u, int v, int vol){
	adj[u].push_back(Eend);Eend->set(u, v, vol);++Eend;
	adj[v].push_back(Eend);Eend->set(v, u, 0);++Eend;
}

inline bool getint(int &x){
	int ch = getc();
	while(!isdigit(ch))ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(ch == '\n' || ch == '\r')return true;
	return false;
}

inline void init(){
	getd(M), getd(N);
	T = M + N + 1;
	int i, to;
	bool end;
	int w[maxn];
	for(i = 1;i <= M;++i){
		getd(w[i]);
		Sum += w[i];
		do{
			end = getint(to);
			AddE(i, M + to, INF);
		}while(!end);
	}
	for(i = M + 1;i < T;++i) getd(w[i]);
	for(i = 1;i <= M;++i)AddE(0, i, w[i]);
	for(i = M + 1;i < T;++i)AddE(i, T, w[i]);
}

inline bool BFS(){
	bool vis[maxn] = {1};
	queue<int> Q;Q.push(0);
	vector<Edge*>::iterator it;
	int cur;
	while(!Q.empty()){
		cur = Q.front();Q.pop();
		for(it = adj[cur].begin();it != adj[cur].end();++it)if((*it)->c && !vis[(*it)->v]){
			vis[(*it)->v] = true;
			h[(*it)->v] = h[cur] + 1;
			Q.push((*it)->v);
		}
	}
	return vis[T];
}

bool vis[maxn] = {1};
void DFS(int cur){
	if(vis[T])return;
	vector<Edge*>::iterator it;
	for(it = adj[cur].begin();it != adj[cur].end();++it)if((*it)->c&&!vis[(*it)->v]&&h[(*it)->v]-h[cur]==1){
		vis[(*it)->v] = true;
		from[(*it)->v] = *it;
		DFS((*it)->v);
	}
}

#define ops(e) (E + ((e - E) ^ 1))

inline void Aug(){
	int Min = INF;
	for(Edge *it = from[T];;it = from[it->u]){
		Min = min(Min, it->c);
		if(it->u == S)break;
	}
	for(Edge *it = from[T];;it = from[it->u]){
		it->c -= Min;
		(ops(it)->c) += Min;
		if(it->u == S)break;
	}
	Ans += Min;
}

void GetAns(int cur, bool *ans){
	ans[cur] = true;
	vector<Edge *>::iterator it;
	for(it = adj[cur].begin();it != adj[cur].end();++it){
		Edge &e = **it;
		if(e.v && e.c && !ans[e.v])GetAns(e.v, ans);
	}
}

inline void work(){
	bool cont;
	while(BFS()){
		cont = true;
		while(cont){
			memset(vis + 1, 0, sizeof(bool) * (T + 1));
			DFS(0);
			if(!vis[T]){
				cont = false;
				break;
			}
			Aug();
		}
	}
	bool inAns[maxn] = {0};
	int i;
	GetAns(0, inAns);
	for(i = 1;i <= M;++i)if(inAns[i])fprintf(out, "%d ", i);
	fputc('\n', out);
	for(;i < T;++i)if(inAns[i])fprintf(out, "%d ", i - M);
	fputc('\n', out);
	fprintf(out, "%d\n", Sum - Ans);
}

int main(){
	init();
	work();
	#ifdef DEBUG
	printf("\n%.2lfsec\n", (double)clock() / CLOCKS_PER_SEC);
	#endif
	return 0;
}