记录编号	149156	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 圆桌聚餐	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2015-02-20 02:38:46	内存使用	0.80 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("roundtable.in", "r");
FILE *out = fopen("roundtable.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 = 272, maxm = 152, maxp = (maxn + maxm)<<1, INF = 0x3f3f3f3f;
struct Edge{
	int u, v, c;
	inline void set(int fr, int to, int vol){u = fr, v = to, c = vol;}
}E[maxn*maxm], *Eend = E, *from[maxp];

int M, N, T, Ans, Sum, h[maxp];

vector<Edge*> adj[maxp];

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 void init(){
	getd(M), getd(N);
	T = M + N + 1;
	int w, i, j;
	for(i = 1;i <= M;++i){
		getd(w);Sum += w;
		AddE(0, i, w);
	}
	for(i = M+1;i < T;++i){
		getd(w);
		AddE(i, T, w);
	}
	for(i = 1;i <= M;++i)for(j = M+1;j < T;++j)AddE(i, j, 1);
}

inline bool BFS(){
#ifdef DEBUG
	fprintf(out, "BFSing\n");
#endif
	bool vis[maxp] = {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[maxp] = {1};
void DFS(int cur){
#ifdef DEBUG
	fprintf(out, "DFSing\n");
#endif
	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)break;
	}
	for(Edge *it = from[T];;it = from[it->u]){
		it->c -= Min;
		(ops(it)->c) += Min;
		if(!it->u)break;
	}
	Ans += Min;
}

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();
		}
	}
	if(Ans < Sum){fprintf(out, "0\n");return;}
	fprintf(out, "1\n");
	vector<Edge *>::iterator it;
	for(int i = 1;i <= M;++i){
		for(it = adj[i].begin();it != adj[i].end();++it){
			Edge &e = **it;
			if(!e.v || e.c)continue;
			fprintf(out, "%d ", e.v - M);
		}
		fputc('\n', out);
	}
}

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