\(\mathtt{CF 687D}\)

\(\mathcal{Description}\)

给你一个图有 \(n\) 个点 \((1 \leq n \leq 10^3)\) 和 \(m\) 条边 \((1 \leq m \leq \dfrac{n*(n-1)}{2})\) ，边有边权。给定 \(q\) 组询问，每次询问给定 \(l\) 和 \(r\)，用编号为 \([l,r]\) 去构成图，使得两边端点在同一个部分的边的最大值最小。

\(\mathcal{Solution}\)

看到题第一反应是线段树，看看标签好像不太对劲的样子，考虑简单点的做法。

考虑如果构成的图是二分图的话，不可能存在一条边的两个端点在同一部分，所以可以得出构成的图一定不是二分图，于是题目可以转化成找奇环的最小变的最大值。

我们可以把边按权值从大到小排序，从最大的开始，不断加边，如果当前构成的图还是一个二分图，则继续加边，如果不是，就是最后我们要构成的图，所以就可以用带权二分图来做。

\(\mathcal{Code}\)

#include<bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;

int n, m, q;

int fa[N], fa1[N];

struct Node {

	int u, v, w, id;

} edge[N << 1];

inline int read() {

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

	for (; c < 48 || c > 57; c = getchar()) k ^= (c == '-');

	for (; c >= 48 && c <= 57; c = getchar()) x = x * 10 + (c ^ 48);

	return k ? x : -x;

}

inline bool cmp(Node x, Node y) {

	return x.w > y.w;

}

int find(int x) {

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

}

inline void match(int x, int y) {

	int fx = find(x), fy = find(y);

	if (fx == fy)

		return;

	if (fa1[fx] < fa1[fy]) swap(fx, fy);

	fa[fy] = fa[fx];

	if (fa1[fx] == fa1[fy])

		fa1[fx]++;

	return;

}

inline int query(int l, int r) {

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

		if (edge[i].id < l || edge[i].id > r)

			continue;

		if (find(edge[i].u) != find(edge[i].v)) {

			match(edge[i].u, edge[i].v + n);

			match(edge[i].u + n, edge[i].v);

		}

		else

			return edge[i].w;

	}

	return -1;

}

int main() {

    n = read(), m = read(), q = read();

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

		edge[i].u = read(), edge[i].v = read(), edge[i].w = read(), edge[i].id = i;

	std::sort(edge + 1, edge + 1 + m, cmp);

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

		fa[i] = i, fa1[i] = 0;

	for (int l = 0, r = 0, ans = -1; q--; ) {

		l = read(), r = read();

		printf("%d\n", query(l, r));

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

			fa[i] = i, fa1[i] = 0;

	}

	return 0;

}

巴特西

CF687D Dividing Kingdom II

\(\mathtt{CF 687D}\)

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章