题解：P11360 [CEOI 2015] 管道

题目大意

求割边。空间限制：16MB。

1 \le n \le 10 ^ 5

，

1 \le m \le 6 \times 10 ^ 6

题目分析

由于卡空间，所以我们不能用 Tarjan。

注意到：割边一定在原图的 每一个生成树 上面。

拿样例举例。

(1, 8)

这条边一定在左边这个连通块的每一个生成树上。

如果把

(1, 8)

和

(9, 10)

这两条割边删掉，我们会发现整个图变成两块，

\{1, 6, 7\}

和

\{2, 3, 4, 5, 8\}

。先叫它们为 “割块”。

我们给每个点设一个权值

a

。

我们发现对于一条非树边

(u, v)

，如果让

a_u

加上一个随机权值

w

，

a_v

减去

w

，那么在

lca(u, v)

处这条边就不会再造成影响了。而如果

v

的子树上的所有非树边都不造成影响了即

a_v = 0

时，意味着

v

的子树就是一个“割块”，所以

(fa_v, v)

就是一条割边。

code

CPP

#include <bits/stdc++.h>
#define ft first
#define sd second
#define endl '\n'
#define pb push_back
#define md make_pair
#define gc() getchar()
#define pc(ch) putchar(ch)
#define umap unordered_map
#define pque priority_queue
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 bint;
typedef pair<int, int> pii;
typedef pair<pii, int> pi1;
typedef pair<pii, pii> pi2;
const ll INF = 0x3f3f3f3f;
const db Pi = acos(-1.0);
inline ll read()
{
	ll res = 0, f = 1; char ch = gc();
	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = gc();
	while (ch >= '0' && ch <= '9') res = (res << 1) + (res << 3) + (ch ^ 48), ch = gc();
	return res * f;
}
inline void write(ll x)
{
	if (x < 0) x = -x, pc('-');
	if (x > 9) write(x / 10);
	pc(x % 10 + '0');
}
inline void writech(ll x, char ch) { write(x), pc(ch); }
const int N = 1e5 + 5;
mt19937 Rand(time(0)); // 随机 
vector<int> e[N]; // 存生成树
int fa[N], siz[N]; // 并查集 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int a[N]; // 权值 
void dfs(int u, int fa)
{
	for (int v : e[u])
	{
		if (v == fa) continue;
		dfs(v, u), a[u] += a[v];
		if (a[v] == 0) writech(u, ' '), writech(v, '\n'); // "割块"
	}
}
int main()
{
	int n = read(), m = read();
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++)
	{
		int u = read(), v = read();
		int s = find(u), t = find(v);
		if (s != t) // 加入生成树 
		{
			if (siz[s] > siz[t]) swap(s, t);
			fa[s] = t, siz[t] += siz[s];
			e[u].pb(v); e[v].pb(u);
		}
		else 
		{
			int w = Rand(); // 随机 
			a[u] += w, a[v] -= w;
		}
	}
	for (int i = 1; i <= n; i++) if (fa[i] == i) dfs(i, 0); // 一个连通块 
	return 0;
}

题解：P11360 [CEOI 2015] 管道

文章操作

题目大意

题目分析

code

相关推荐

评论

题解：P11360 [CEOI 2015] 管道