题目链接:nowcoder多校8-Explorer
题意:
给一个无向图,每条边上有一个区间限制,只有在区间内的数能够通过该边,问从1号点出发,有多少数能到达n号点。
题解:
线段树维护区间,用并查集维护点的连通性。
对于每条边上的区间,将其离散化之后加入线段树中,然后从根节点开始向下dfs,把同一区间内的边取出来,判断1号点与n号点是否连通,并查集需要按秩合并进行优化。
参考代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5;
int n, m, ans;
int fa[MAXN], sz[MAXN];
int uu[MAXN], vv[MAXN], ll[MAXN], rr[MAXN], tmp[MAXN << 2];
vector<int> a[MAXN << 3];
int getf(int x)
{
if (x == fa[x])
return x;
return getf(fa[x]);
}
void seg_update(int L, int R, int val, int l, int r, int rt)
{
if (L <= l && r <= R)
{
a[rt].push_back(val);
return;
}
int mid = (l + r) >> 1;
if (L <= mid)
seg_update(L, R, val, l, mid, rt << 1);
if (R > mid)
seg_update(L, R, val, mid + 1, r, rt << 1 | 1);
}
void dfs(int l, int r, int rt)
{
vector<int> vec;
vec.clear();
for (int i = 0; i < a[rt].size(); i++)
{
int now = a[rt][i];
int u = uu[now], v = vv[now];
u = getf(u), v = getf(v); //并查集按秩合并
if (sz[u] > sz[v])
swap(u, v);
fa[u] = v;
sz[v] += sz[u];
vec.push_back(u);
}
int mid = (l + r) >> 1;
if (getf(1) == getf(n))
ans += tmp[r + 1] - tmp[l];
else if (l < r)
{
dfs(l, mid, rt << 1);
dfs(mid + 1, r, rt << 1 | 1);
}
for (int i = 0; i < vec.size(); i++)
{
int x = vec[i];
fa[x] = x;
}
vec.clear();
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
fa[i] = i, sz[i] = 1;
int cnt = 0;
for (int i = 1; i <= m; i++)
{
scanf("%d%d%d%d", &uu[i], &vv[i], &ll[i], &rr[i]);
tmp[++cnt] = ll[i];
tmp[++cnt] = rr[i] + 1;
}
sort(tmp + 1, tmp + 1 + cnt);
cnt = unique(tmp + 1, tmp + 1 + cnt) - (tmp + 1);
for (int i = 1; i <= m; i++)
{
ll[i] = lower_bound(tmp + 1, tmp + 1 + cnt, ll[i]) - tmp;
rr[i] = lower_bound(tmp + 1, tmp + 1 + cnt, rr[i] + 1) - tmp;
seg_update(ll[i], rr[i] - 1, i, 1, cnt - 1, 1);
}
dfs(1, cnt - 1, 1);
printf("%d\n", ans);
return 0;
}