POJ1149 PIGS

想了好久啊。。。（#－.－）

开始想到m*n个点的构图，明显超时，于是考虑压缩节点个数

我们发现每个猪圈最后被有且只有一个人调整，于是想到对于一个人，连接他能调整的每个猪圈的上一个控制人。（不懂可以开代码  (・(ｪ)・)   )

/**
 * Problem:POJ1149
 * Author:Shun Yao
 * Time:2013.9.13
 * Result:
 * Memo:
 */
 
#include <cstring>
#include <cstdio>

#define INF 0x7fffffff
#define MAXT 1111

long m, n, s, t, f[MAXT], p2[MAXT], h[MAXT], sum[MAXT];

class Edge {
public:
	long v, f;
	Edge *op, *next;
	Edge() {}
	~Edge() {}
	Edge(long V, long F, Edge *o, Edge *ne) : v(V), f(F), op(o), next(ne) {}
} *g[MAXT], *now[MAXT], *p1[MAXT];

void add(long x, long y, long c) {
	g[x] = new Edge(y, c, 0, g[x]);
	g[y] = new Edge(x, 0, g[x], g[y]);
	g[x]->op = g[y];
}

long *l, *r, q[MAXT];
void SAP() {
	static char f;
	static Edge *e;
	static long i, ans, ww, w;
	memset(h, -1, sizeof h);
	memset(sum, 0, sizeof sum);
	l = r = q;
	*r++ = t;
	h[t] = 0;
	sum[0] = 1;
	while (l < r) {
		for (e = g[*l]; e; e = e->next)
			if (h[e->v] == -1) {
				++sum[h[e->v] = h[*l] + 1];
				*r++ = e->v;
			}
		++l;
	}
	for (i = 0; i <= t; ++i) {
		now[i] = g[i];
		p1[i] = 0;
		p2[i] = -1;
	}
	i = s;
	ans = 0;
	while (h[s] <= t) {
		f = 0;
		for (e = now[i]; e; e = e->next)
			if (e->f > 0 && h[i] == h[e->v] + 1) {
				now[i] = e;
				p1[e->v] = e;
				p2[e->v] = i;
				i = e->v;
				if (i == t) {
					ww = INF;
					for (w = t; w != s; w = p2[w])
						if (ww > p1[w]->f)
							ww = p1[w]->f;
					for (w = t; w != s; w = p2[w]) {
						p1[w]->f -= ww;
						p1[w]->op->f += ww;
					}
					ans += ww;
					i = s;
				}
				f = 1;
				break;
			}
		if (!f) {
			ww = t + 1;
			for (e = g[i]; e; e = e->next)
				if (e->f > 0 && ww > h[e->v]) {
					ww = h[e->v];
					now[i] = e;
				}
			++sum[ww > t ? ww : ++ww];
			if (!--sum[h[i]])
				break;
			h[i] = ww;
			if (i != s)
				i = p2[i];
		}
	}
	printf("%ld", ans);
}

int main() {
	static long i, j, k, A, B;

#ifndef ONLINE_JUDGE
	freopen("poj1149.in", "r", stdin);
	freopen("poj1149.out", "w", stdout);
#endif

	scanf("%ld%ld", &m, &n);
	s = 0;
	t = n + m + 1;
	for (i = 1; i <= m; ++i) {
		scanf("%ld", &A);
		add(s, i, A);
		f[i] = i;
	}
	for (i = 1; i <= n; ++i) {
		scanf("%ld", &A);
		for (j = 1; j <= A; ++j) {
			scanf("%ld", &k);
			add(f[k], i + m, INF);
			f[k] = i + m;
		}
		scanf("%ld", &B);
		add(i + m, t, B);
	}
	SAP();

	fclose(stdin);
	fclose(stdout);
	return 0;
}