[C++知识库]P3756 [CQOI2017]老C的方块

题面自己看吧。。。

std

典型的网络流。

看到网格和炸点，可以想到是最小割。

按照套路，考虑染色，寻找规律。

发现，可用如下方法染色。

之后四种情况都是如下：

发现如图每种情况必然包含四种不一样的颜色，且顺序都是 黄 $\to$ 绿 $\to$ 黑 $\to$ 灰。

思考一下，发现破坏一个讨厌的图形有以下几种方式：

• 炸掉一个绿色块或黑色块。
• 炸掉所有和绿色块或者黑色块相邻的黄色块或者灰色块。

那么现在模型就很显然了：

1. $s$ 向黄色块连容量为消除黄色块的代价的边。
2. 黄色块向绿色块连容量为 $+\infty$ 的边。
3. 绿色块向蓝线连容量为消除绿色块的代价的边。
4. 蓝线向黑色块连容量为消除黑色块的代价的边。
5. 黑色块向灰色块连容量为 $+\infty$ 的边。
6. 灰色块向 $t$ 连容量为消除灰色块的代价的边。

容易发现第 $3$ 种边和第 $4$ 种边可以合为：绿色块向黑色块连容量为消除绿色块的代价和消除黑色块的代价的最小值的边。

最后跑一边最小割即可。

#include <bits/stdc++.h>

using namespace std;

inline int read()
{
	int x = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

inline void write(int x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

typedef int tp;

const int _ = 5e5 + 10;

int n, m, s, t, lv[_], cur[_];

int tot = 1, head[_], to[_ << 1], nxt[_ << 1];

tp w[_ << 1];

inline void add(int u, int v, tp dis)
{
	to[++tot] = v;
	nxt[tot] = head[u];
	w[tot] = dis;
	head[u] = tot;
}

inline void Add(int u, int v, tp dis)
{
	add(u, v, dis);
	add(v, u, 0);
}

inline bool bfs()
{
	memset(lv, -1, sizeof(lv));
	lv[s] = 0;
	memcpy(cur, head, sizeof(head));
	queue<int> q;
	q.push(s);
	while (!q.empty())
	{
		int p = q.front();
		q.pop();
		for (int eg = head[p]; eg; eg = nxt[eg])
		{
			int v = to[eg];
			tp vol = w[eg];
			if (vol > 0 && lv[v] == -1)
				lv[v] = lv[p] + 1, q.push(v);
		}
	}
	return lv[t] != -1;
}

tp dfs(int p = s, tp flow = 2e9)
{
	if (p == t)
		return flow;
	tp rmn = flow;
	for (int eg = cur[p]; eg && rmn; eg = nxt[eg])
	{
		cur[p] = eg;
		int v = to[eg];
		tp vol = w[eg];
		if (vol > 0 && lv[v] == lv[p] + 1)
		{
			tp c = dfs(v, min(vol, rmn));
			rmn -= c;
			w[eg] -= c;
			w[eg ^ 1] += c;
		}
	}
	return flow - rmn;
}

inline tp dinic()
{
	tp ans = 0;
	while (bfs())
		ans += dfs();
	return ans;
}

int r, c, x[_], y[_], W[_], col[_];

inline long long tr(int i, int j) { return (long long)(i - 1) * (c + 1) + j; }

map<long long, int> mp;

int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1};

inline void build_A(int i, int j, int d)
{
	for (int k = 0; k < 4; k++)
	{
		int px = dx[k] + i, py = dy[k] + j;
		int num = mp[tr(px, py)];
		if (num != 0)
		{
			if (col[num] != 2)
				Add(num, d, 2e9);
			else
				Add(d, num, min(W[num], W[d]));
		}
	}
}
inline void build_B(int i, int j, int d)
{
	for (int k = 0; k < 4; k++)
	{
		int px = dx[k] + i, py = dy[k] + j;
		int num = mp[tr(px, py)];
		if (num != 0)
		{
			if (col[num] != 1)
				Add(d, num, 2e9);
		}
	}
}

signed main()
{
	c = read(), r = read(), n = read();
	for (int i = 1; i <= n; i++)
	{
		x[i] = read(), y[i] = read(), W[i] = read();
		mp[tr(x[i], y[i])] = i;
	}
	s = 0, t = _ - 1;
	for (int i = 1; i <= n; i++)
	{
		switch (x[i] % 4)
		{
		case 1:
		{
			col[i] = (y[i] % 2) ? 1 : 3;
			break;
		}
		case 2:
		{
			col[i] = (y[i] % 2) ? 2 : 4;
			break;
		}
		case 3:
		{
			col[i] = (y[i] % 2) ? 4 : 2;
			break;
		}
		case 0:
		{
			col[i] = (y[i] % 2) ? 3 : 1;
			break;
		}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		switch (col[i])
		{
		case 1:
		{
			build_A(x[i], y[i], i);
			break;
		}
		case 2:
		{
			build_B(x[i], y[i], i);
			break;
		}
		case 3:
		{
			Add(s, i, W[i]);
			break;
		}
		case 4:
		{
			Add(i, t, W[i]);
			break;
		}
		}
	}
	write(dinic());
	return 0;
}