BZOJ1001或洛谷4001 [BJOI2006]狼抓兔子

BZOJ原题链接

洛谷原题链接

显然就是求最小割。

而对于一个平面图有结论，最大流=最小割=对偶图最短路。

所以这题可用最大流或是转换为对偶图求最短路，这里我是用的对偶图。

虽然理论上按上界算，这题\(Dinic\)应该是跑不过去的，不过因为网络流复杂度玄学，\(Dinic\)莫名跑得挺快的。

在转换对偶图的时候，注意\(n = 1\)或\(m = 1\)的情况。

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N = 2e6 + 10;

const int M = 7e6 + 10;

struct po {

	int x, d;

	bool operator < (const po &b) const

	{

		return d > b.d;

	}

};

po X;

int fi[N], di[M], ne[M], da[M], dis[N], l, st, ed, n, m;

bool v[N];

priority_queue<po>q;

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline void add(int x, int y, int z)

{

	di[++l] = y;

	da[l] = z;

	ne[l] = fi[x];

	fi[x] = l;

	di[++l] = x;

	da[l] = z;

	ne[l] = fi[y];

	fi[y] = l;

}

inline int ch(int x, int y, int L)

{

	int k = ((x - 1) * (m - 1) + y) << 1;

	return L ? k - 1 : k;

}

inline void add_row(int x, int y, int z)

{

	if (!(x ^ 1))

		add(ch(x, y, 0), ed, z);

	else

		if (!(x ^ n))

			add(st, ch(x - 1, y, 1), z);

		else

			add(ch(x - 1, y, 1), ch(x, y, 0), z);

}

inline void add_col(int x, int y, int z)

{

	if (!(y ^ 1))

		add(st, ch(x, y, 1), z);

	else

		if (!(y ^ m))

			add(ch(x, y - 1, 0), ed, z);

		else

			add(ch(x, y - 1, 0), ch(x, y, 1), z);

}

inline void add_opl(int x, int y, int z)

{

	add(ch(x, y, 1), ch(x, y, 0), z);

}

int main()

{

	int i, j, x, y;

	n = re();

	m = re();

	st = (n - 1) * (m - 1) << 1 | 1;

	ed = st + 1;

	if (!(n ^ 1) || !(m ^ 1))

	{

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

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

				add(st, ed, re());

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

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

				add(st, ed, re());

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

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

				add(st, ed, re());

	}

	else

	{

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

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

				add_row(i, j, re());

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

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

				add_col(i, j, re());

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

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

				add_opl(i, j, re());

	}

	memset(dis, 60, sizeof(dis));

	X.d = dis[X.x = st] = 0;

	q.push(X);

	while (!q.empty())

	{

		x = q.top().x;

		q.pop();

		if (v[x])

			continue;

		v[x] = 1;

		for (i = fi[x]; i; i = ne[i])

			if (dis[X.x = y = di[i]] > dis[x] + da[i])

			{

				X.d = dis[y] = dis[x] + da[i];

				q.push(X);

			}

	}

	printf("%d", dis[ed]);

	return 0;

}

巴特西

BZOJ1001或洛谷4001 [BJOI2006]狼抓兔子

BZOJ原题链接

洛谷原题链接

最新文章

热门文章