记录编号	235683	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 太空飞行计划	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-03-11 12:02:45	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn = 203;
const int inf = 1e9;
struct edge {
	int to, ne, le;
}e[maxn*5];
int head[maxn], tot = 0;
void addedge(int a, int b, int c) {
	++tot; e[tot].to = b; e[tot].le = c; e[tot].ne = head[a]; head[a] = tot;
	++tot; e[tot].to = a; e[tot].ne = head[b]; head[b] = tot;
}

const char nel = '\n';
const char lnel = '\r';
int n ,m;
int sum;

int get_num() {
	char tmp;
	int ans = 0;
	tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp >= '0' && tmp <= '9') {
		ans = ans*10+tmp-'0';
		tmp = getchar();
	}
	return ans;
}
void get_line(int i) {
	char tmp;
	int ans = 0;
	tmp = getchar();
	while(true) {
		if(tmp == nel || tmp == lnel) {
			if(ans) addedge(i, ans+n, inf);
			break;
		}
		if(tmp < '0' || tmp >'9') {
			if(ans) addedge(i, ans+n, inf);
			ans = 0;
			tmp = getchar();
			continue;
		} 
		ans = ans*10 + tmp -'0';
		tmp = getchar();
	}
}
void read() {
	n = get_num(); m = get_num();
	int a, b;
	char c;
	for(int i = 1; i <= n; i++) {
		a = get_num();
		get_line(i);
		addedge(n+m+1, i, a);
		sum += a;
	}
	for(int i = 1; i <= m; i++) {
		a = get_num();
		addedge(n+i, n+m+2, a);
	}
} 

short de[maxn];
bool bfs() {
	memset(de, 0, sizeof(de));
	queue<int> q;
	while(!q.empty()) q.pop();
	q.push(n+m+1);
	de[n+m+1] = 1;
	int now, to;
	while(!q.empty()) {
		now = q.front();
		q.pop();
		for(int i = head[now]; i; i = e[i].ne) {
			to = e[i].to;
			if((!de[to]) && e[i].le) {
				de[to] = de[now]+1;
				q.push(to);
			}
		}
	}
	return de[n+m+2];
}
int dfs(int now, int min_flow) {
	if(now == n+m+2) return min_flow;
	int to, now_min;
	for(int i = head[now]; i; i = e[i].ne) {
		to = e[i].to;
		if(de[to] != de[now]+1 || !e[i].le) continue;
		now_min = dfs(to, min(min_flow, e[i].le));
		if(!now_min) continue;
		e[i].le -= now_min;
		if(i&1) {
			e[i+1].le += now_min; 
		} else {
			e[i-1].le += now_min;
		}
		return now_min;
	}
	return 0;
}
int dinic() {
	int ans = 0, tmp;
	while(bfs()) {
		while(tmp = dfs(n+m+1, inf)) ans += tmp;
	}
	return ans;
} 

bool usel[maxn], user[maxn];

void get_ans(int now) {
	int to;
	de[now] = true;
	if(now <= n) usel[now] = true;
	else user[now-n] = true;
	for(int i = head[now]; i; i = e[i].ne) {
		if(e[i].le <= 0) continue;
		to = e[i].to;
		if(de[to] || to == n+m+2) continue;
		get_ans(to);
	}
}

void solve() {
	int ans;
	ans = dinic();
	memset(de, 0, sizeof(de));
	get_ans(n+m+1);
	
	for(int i = 1; i <= n; i++) {
		if(usel[i]) printf("%d ", i);
	}
	printf("\n");
	for(int i = 1; i <= m; i++) {
		if(user[i]) printf("%d ", i);
	}
	printf("\n%d\n", sum-ans);
}
int main() {
	freopen("shuttle.in", "r", stdin);
	freopen("shuttle.out", "w", stdout);
	read();
	solve();
	return 0;
}