我开的各种数组自己测试的时候只有700k，而且队列后来也换成了手写的，不明白为什么会爆空间
代码如下：

#include <cstdio>

#define REP(i, s, t) for (int i = (s); i <= (t); i++)

const int INF = (int)2e9;
const int N = (int)2e2 + 50;
const int M = (int)3e4 + 50;
const int S = (int)1e3 + 50;

inline int min(int a, int b)
{
	return a < b ? a : b;
}

int head[N], cnt = 1;
struct edge {int to, next, v;} e[M];
inline void ins(int x, int y, int v)
{
	e[++cnt] = (edge){y, head[x], v}; head[x] = cnt;
	e[++cnt] = (edge){x, head[y], 0}; head[y] = cnt;
}

int q[N], sq, tq;
int n, s, lev[N], cur[N];
bool bfs()
{
	REP(i, 1, n)
		lev[i] = -1;
	lev[1] = 0;
	sq = tq = 1;
	q[tq++] = 1;
	while (sq != tq) {
		int x = q[sq++];
		for (int i = head[x]; i; i = e[i].next) {
			if (e[i].v && lev[e[i].to] == -1) {
				lev[e[i].to] = lev[x] + 1;
				q[tq++] = e[i].to;
			}
		}
	}
	return lev[n] != -1;
}

bool vst[N][N];
int dfs(int x, int lim)
{
	if (x == n)
		return lim;
	int usd = 0;
	for (int i = cur[x]; i; i = e[i].next) {
		int tmp = dfs(e[i].to, min(e[i].v, lim - usd));
		e[i].v -= tmp;
		if (e[i].v)
			cur[x] = i;
		e[i^1].v += tmp;
		usd += tmp;
		if (usd == lim)
			return lim;
	}
	if (!usd)
		lev[x] = -1;
	return usd;
}

int dinic()
{
	int maxflow = 0;
	while (bfs()) {
		REP(i, 1, n) {
			cur[i] = head[i];
		}
		maxflow += dfs(1, INF);
	}
	return maxflow;
}

int d[S], p[S];
void input()
{
	scanf("%d%d", &s, &n);
	REP(i, 1, s)
		scanf("%d", &d[i]);
	REP(i, 1, n) {
		int a, k, v = 0;
		scanf("%d", &k);
		REP(j, 1, k) {
			scanf("%d", &a);
			if (p[a] == 0) {
				v += d[a];
				p[a] = i;
			} else {
				if (!vst[p[a]][i]) {
					ins(p[a] + 1, i + 1, INF);
					vst[p[a]][i] = vst[i][p[a]] = 1;
				}
				p[a] = i; //关键，且不能放到里面
			}
		}
		if (v)
			ins(1, i + 1, v);
		scanf("%d", &v);
		ins(i + 1, n + 2, v);
	}
	n += 2;
}

void go()
{
	int ans = dinic();
	printf("%d\n", ans);
}

int main()
{
	input(); go();
	return 0;
}

• Re:明明有10000K空间的啊，我怎么会爆空间呢？ (2238) 1216822876 2016-06-14 18:04:50