[洛谷P3227][HNOI2013]切糕

题目大意：有一个$n\times m$的切糕，每一个位置的高度可以在$[1,k]$之间，每个高度有一个代价，要求四联通的两个格子之间高度最多相差$D$，问可行的最小代价。$n,m,k,D\leqslant 40$

题解：网络流，不考虑相差为$D$的条件时，可以给每个位置建一个点，源点连向高度为$1$的点容量为$\infty$，高度为$i$的点连向这个位置高度为$i+1$的点，容量为代价，高度为$k$的连向汇点，容量为代价。跑最小割。

考虑相差为$D$的条件，可以对于相邻的两个点$A,B$，连接$A_i\to B_{i-D}$的容量为$\infty$的边这样就强制限定两个点的最小割必须相距小于等于$D$，跑最小割即可

卡点：加边的时候多加了$k$倍，导致又$TLE$又$RE$

C++ Code：

#include <cstdio>

#include <cctype>

#include <algorithm>

const int inf = 0x3f3f3f3f;

namespace std {

	struct istream {

#define M (1 << 24 | 3)

		char buf[M], *ch = buf - 1;

		inline istream() { fread(buf, 1, M, stdin); }

		inline istream& operator >> (int &x) {

			while (isspace(*++ch));

			for (x = *ch & 15; isdigit(*++ch); ) x = x * 10 + (*ch & 15);

			return *this;

		}

#undef M

	} cin;

	struct ostream {

#define M (1 << 10 | 3)

		char buf[M], *ch = buf - 1;

		inline ostream& operator << (int x) {

			if (!x) {*++ch = '0'; return *this;}

			static int S[20], *top; top = S;

			while (x) {*++top = x % 10 ^ 48; x /= 10;}

			for (; top != S; --top) *++ch = *top;

			return *this;

		}

		inline ostream& operator << (const char x) {*++ch = x; return *this;}

		inline ~ostream() { fwrite(buf, 1, ch - buf + 1, stdout); }

#undef M

	} cout;

}

namespace Network_Flow {

	const int maxn = 50 * 50 * 50, maxm = maxn * 6;

	int lst[maxn], head[maxn], cnt = 1;

	struct Edge {

		int to, nxt, w;

	} e[maxm << 1];

	void addedge(int a, int b, int c) {

		e[++cnt] = (Edge) { b, head[a], c }; head[a] = cnt;

		e[++cnt] = (Edge) { a, head[b], 0 }; head[b] = cnt;

	}

	int st, ed, n, MF;

	int GAP[maxn], dis[maxn], q[maxn], h, t;

	void init() {

		GAP[dis[q[h = t = 0] = ed] = 1] = 1;

		for (int i = st; i <= ed; ++i) lst[i] = head[i];

		while (h <= t) {

			int u = q[h++];

			for (int i = head[u], v; i; i = e[i].nxt) {

				v = e[i].to;

				if (!dis[v]) {

					++GAP[dis[v] = dis[u] + 1];

					q[++t] = v;

				}

			}

		}

	}

	int dfs(int u, int low) {

		if (!low || u == ed) return low;

		int w, res = 0;

		for (int &i = lst[u], v; i; i = e[i].nxt) if (e[i].w) {

			v = e[i].to;

			if (dis[u] == dis[v] + 1) {

				w = dfs(v, std::min(low, e[i].w));

				res += w, low -= w;

				e[i].w -= w, e[i ^ 1].w += w;

				if (!low) return res;

			}

		}

		if (!--GAP[dis[u]]) dis[st] = n + 1;

		++GAP[++dis[u]], lst[u] = head[u];

		return res;

	}

	void ISAP(int S, int T) {

		st = S, ed = T, n = T - S + 1;

		init(); while (dis[st] <= n) MF += dfs(st, inf);

	}

}

int n, m, h, D;

int v[50][50][50];

int pos[50][50][50], idx, st, ed;

void addedge(int x, int y, int z, int w) {

	for (int i = D + 1; i <= h; ++i)

		Network_Flow::addedge(pos[x][y][i], pos[z][w][i - D], inf);

}

int main() {

	std::cin >> n >> m >> h >> D;

	for (int i = 1; i <= h; ++i)

		for (int j = 1; j <= n; ++j)

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

				pos[j][k][i] = ++idx;

				std::cin >> v[j][k][i];

			}

	st = 0, ed = ++idx;

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

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

			for (int k = 1; k <= h; ++k) {

				if (k == 1) Network_Flow::addedge(st, pos[i][j][k], inf);

				if (k == h) Network_Flow::addedge(pos[i][j][k], ed, v[i][j][k]);

				else Network_Flow::addedge(pos[i][j][k], pos[i][j][k + 1], v[i][j][k]);

			}

			if (i != 1) addedge(i, j, i - 1, j);

			if (i != n) addedge(i, j, i + 1, j);

			if (j != 1) addedge(i, j, i, j - 1);

			if (j != n) addedge(i, j, i, j + 1);

		}

	Network_Flow::ISAP(st, ed);

	std::cout << Network_Flow::MF << '\n';

	return 0;

}

巴特西

[洛谷P3227][HNOI2013]切糕

最新文章

热门文章