[题解] [AtCoder2134] Zigzag MST

题面

题解

考虑kruscal的过程

对于三个点\(x, y, x + 1\), 我们可以将\((x, y, z), (y, x + 1, z + 1)\)看做\((x, y, z), (x, x + 1, z + 1)\)

因为当连完\((x, y, z)\)后, \(x\)与\(y\)已经联通, 所以\((y, x + 1, z + 1)\)和\((x, x + 1, z + 1)\)是等价的

所以对于每个连边操作, 我们就变成了连一条边和一个环

考虑怎么优化环上的边的数量

对于这两条边\((x, x + 1, z + 1), (x + 1, x + 2, z + 3)\)

可以发现第二条边的权值就是第一条边的权值+2

所以我们可以用\(f[i]\)代表\(i\)到\(i \% n + 1\)中边权最小的边, 然后更新一圈, 跑一遍最小生成树即可

Code

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <vector>

#define itn int

#define reaD read

#define N 200001

using namespace std;

int n, Q, f[N], cnt, fa[N];

struct edge { int from, to, cost; bool operator < (const edge &p) const { return cost < p.cost; } } e[N << 2];

inline int read()

{

	int x = 0, w = 1; char c = getchar();

	while(c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }

	while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }

	return x * w;

}

inline void adde(int u, int v, int w) { e[++cnt] = (edge) { u, v, w }; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

long long Kruscal()

{

	sort(e + 1, e + cnt + 1);

	long long ans = 0;

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

	{

		int u = find(e[i].from), v = find(e[i].to), w = e[i].cost;

		if(u == v) continue;

		fa[u] = v; ans += w;

	}

	return ans;

}

int main()

{

	n = read(); Q = read();

	for(int i = 1; i <= n; i++) fa[i] = i;

	memset(f, 0x3f, sizeof(f));

	while(Q--)

	{

		int u = read() + 1, v = read() + 1, w = reaD();

		adde(u, v, w);

		f[u] = min(f[u], w + 1); f[v] = min(f[v], w + 2);

	}

	int pos = 1;

	for(int i = 2; i <= n; i++) if(f[i] < f[pos]) pos = i;

	for(int i = pos; i <= pos + n - 1; i++) f[i % n + 1] = min(f[i % n + 1], f[(i - 1) % n + 1] + 2);

	for(int i = 1; i <= n; i++) adde(i, i % n + 1, f[i]);

	printf("%lld\n", Kruscal());

	return 0;

}