_bzoj1001 [BeiJing2006]狼抓兔子【平面图】

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1001

顺便推荐一个ppt，里面有对平面图的介绍：浅析最大最小定理在信息学竞赛中的应用。

这里直接求最小割肯定会T，所以应把原图看成一张平面图，ppt中说该平面图对应的对偶图的每一个环对应原图的一个割，这点有些不理解，不过不影响做这一道题。想象一下，在最外面那个无限大的平面，由左上角朝右下角连一条附加的边，这么做就多了一个附加面，设这条附加的边的权值为 -inf，那么最小割一定包含这一条边。把这条边去掉，就成了求一个最短路的问题了。

#include <cstdio>

#include <cstring>

const int maxn = 1005, maxnd = maxn * maxn << 1, maxe = maxn * maxn * 3;

int n, m, S, T, special = 2147483647, t1, t2, t3;

int head[maxnd], to[maxe << 1], next[maxe << 1], w[maxe << 1], lb;

char ch;

bool inq[maxnd];

int que[maxnd], h, head_, tail, d[maxnd];

inline void ist(int aa, int ss, int ww) {

	to[lb] = ss;

	next[lb] = head[aa];

	head[aa] = lb;

	w[lb] = ww;

	++lb;

}

inline void readint(int & rt) {

	while ((ch = getchar()) < 48);

	rt = ch - 48;

	while ((ch = getchar()) > 47) {

		rt = rt * 10 + ch - 48;

	}

}

int main(void) {

	//freopen("in.txt", "r", stdin);

	memset(head, -1, sizeof head);

	memset(next, -1, sizeof next);

	readint(n); readint(m);

	if (n == 1 || m == 1) {

		while (scanf("%d", &t1) != EOF) {

			special = special < t1? special: t1;

		}

		printf("%d\n", special);

		return 0;

	}

	S = (n - 1) * (m - 1) * 2 + 1;

	T = S + 1;

	for (int i = 1; i <= n; ++i) {

		for (int j = 1; j < m; ++j) {

			t2 = (i - 1) * (m - 1) * 2 + j * 2;

			t1 = t2 - (m - 1) * 2 - 1;

			t1 = t1 > 0? t1: T;

			t2 = t2 < S? t2: S;

			scanf("%d", &t3);

			ist(t1, t2, t3);

			ist(t2, t1, t3);

		}

	}

	for (int i = 1; i < n; ++i) {

		t2 = (i - 1) * (m - 1) * 2 + 1;

		scanf("%d", &t3);

		ist(S, t2, t3);

		ist(t2, S, t3);

		for (int j = 2; j < m; ++j) {

			t1 = (i - 1) * (m - 1) * 2 + (j - 1) * 2;

			t2 = t1 + 1;

			scanf("%d", &t3);

			ist(t1, t2, t3);

			ist(t2, t1, t3);

		}

		t1 = i * (m - 1) * 2;

		scanf("%d", &t3);

		ist(t1, T, t3);

		ist(T, t1, t3);

	}

	for (int i = 1; i < n; ++i) {

		for (int j = 1; j < m; ++j) {

			t2 = (i - 1) * (m - 1) * 2 + j * 2;

			t1 = t2 - 1;

			scanf("%d", &t3);

			ist(t1, t2, t3);

			ist(t2, t1, t3);

		}

	}

	memset(d, 0x3c, sizeof d);

	que[tail++] = S;

	inq[S] = true;

	d[S] = 0;

	while (head_ != tail) {

		h = que[head_++];

		if (head_ == T) {

			head_ = 0;

		}

		inq[h] = false;

		for (int j = head[h]; j != -1; j = next[j]) {

			if (d[to[j]] > d[h] + w[j]) {

				d[to[j]] = d[h] + w[j];

				if (!inq[to[j]]) {

					inq[to[j]] = true;

					que[tail++] = to[j];

					if (tail == T) {

						tail = 0;

					}

				}

			}

		}

	}

	printf("%d\n", d[T]);

	return 0;

}

巴特西

_bzoj1001 [BeiJing2006]狼抓兔子【平面图】

最新文章

热门文章