并查集扩展应用

A. 货物运输

题目描述

有 \(n\) 座城市和 \(m\) 条双向道路。已知走过每条边所需要的汽油量，\(q\) 次询问，求汽油量为 \(l\) 的车可以在多少对城市之间运送货物。（汽车到达城市会立刻把油全部加满）

题解

这道题没有强制在线，所以可以考虑进行离线。

对于大小为 \(n\) 一个连通块，两两相连的点对一共有 \(\frac{n(n-1)}{2}\)
于是 很难不想到 使用并查集维护连通块的大小，动态更新答案。

# include <bits/stdc++.h> 
using namespace std; 
using namespace IOS; 
typedef long long ll; 
# define int long long 
# define lc u << 1
# define rc u << 1 | 1 
const int N = 100005; 

int n, m, q; 
struct edge 
{
    int u, v, w; 
    bool operator < (const edge &t) const { return w < t.w; }
} e[N]; 
struct query
{
    int l, id; 
    bool operator < (const query &t) const { return l < t.l; }
} Q[N]; 
int fa[N], sz[N]; 
int find_fa (int u) { return u == fa[u] ? u : fa[u] = find_fa (fa[u]); }
int ans; 
void union_fa (int u, int v)
{
    u = find_fa (u), v = find_fa (v); 
    if (u != v)
    {
        fa[v] = u; 
        ans -= sz[u] * (sz[u] - 1) + sz[v] * (sz[v] - 1); 
        sz[u] += sz[v]; 
        ans += sz[u] * (sz[u] - 1); 
	}
}
int res[N]; 
signed main ()
{
    read (n, m, q); 
    for (int i = 1; i <= m; i ++ ) read (e[i].u, e[i].v, e[i].w); 
    sort (e + 1, e + 1 + m); 
    for (int i = 1; i <= q; i ++ )
    {
        read (Q[i].l); 
        Q[i].id = i; 
    }
    sort (Q + 1, Q + 1 + q); 
	for (int i = 1; i <= n; i ++ ) fa[i] = i, sz[i] = 1; 
    for (int i = 1, j = 1; i <= q; i ++ )
    {
        while (j <= m && e[j].w <= Q[i].l) union_fa (e[j].u, e[j].v), j ++ ; 
        res[Q[i].id] = ans; 
	}
    for (int i = 1; i <= q; i ++ ) write (res[i] / 2, '\n'); 
	return 0;
}

B. 银河英雄传说

题目描述

yyc 在一次战斗中，他将 1233 战场划分成 \(30000\) 列，每列依次编号为 \(1, 2,\ldots ,30000\)。之后，他把自己的战舰也依次编号为 \(1, 2, \ldots , 30000\)，让第 \(i\) 号战舰处于第 \(i\) 列。这是初始阵形。当进犯之敌到达时，yyc 会多次发布合并指令。合并指令为 M i j，含义为第 \(i\) 号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第 \(j\) 号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。

然而，cdx 可以通过庞大的情报网络随时监听 yyc 的舰队调动指令。

在 yyc 发布指令调动舰队的同时，cdx 为了及时了解当前 yyc 的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，yyc 的第 \(i\) 号战舰与第 \(j\) 号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。

题解

\(fa_i\) 表示飞船 \(i\) 所在列的队头。
\(d_i\) 表示飞船 \(i\) 到其所在队列队头的距离，则飞船 \(i\)和飞船 \(j\) 之间的飞船数量 \(|d_i-d_j|-1\)。
\(sz_i\) 表示飞船 \(i\) 所在的队列的大小

使用并查集维护即可。

# include <bits/stdc++.h> 
using namespace std; 
using namespace IOS; 
typedef long long ll; 
//# define int long long 
# define lc u << 1
# define rc u << 1 | 1 
const int N = 30005; 

int m; 
int fa[N], sz[N], d[N]; 
int find_fa (int u)
{
    if (u == fa[u]) return fa[u]; 
    int v = find_fa (fa[u]); 
    d[u] += d[fa[u]]; 
    fa[u] = v; 
    return v; 
}
void union_fa (int u, int v)
{
	u = find_fa (u), v = find_fa (v);
	if (u != v) fa[u] = v, d[u] = sz[v], sz[v] += sz[u];
}
signed main ()
{
	for (int i = 1; i < N; i ++ ) fa[i] = i, sz[i] = 1;
	read (m); 
	while (m -- )
	{
		char op; int u, v; read (op, u, v); 
		if (op == 'M') union_fa (u, v);
		else
		{
			int fu = find_fa (u), fv = find_fa (v);
            if (fu != fv) write (-1, '\n'); 
            else write (max (0, abs (d[u] - d[v]) - 1), '\n');
		}
	}
	return 0;
}

C. 罗马游戏

题目描述

监狱里面有 \(n\) 个人，每个人都是一个独立的团。最近统计了每个人善良程度。狱卒可以发两种命令：

1. Merge(i, j)。把 \(i\) 所在的团和j所在的团合并成一个团。如果 \(i, j\) 有一个人是死人，那么就忽略该命令。
2. Kill(i)。把 \(i\)所在的团里面善良程度最低的人杀死。如果 \(i\) 这个人已经死了，这条命令就忽略。 狱卒希望他每发布一条 kill 命令，下面的刀斧手就把被杀的人的善良程度报上来。（如果这条命令被忽略，那么就报 \(0\)）

题解

启发式合并+并查集

# include <bits/stdc++.h> 
using namespace std; 
using namespace IOS; 
typedef long long ll; 
//# define int long long 
# define lc u << 1
# define rc u << 1 | 1 
const int N = 1000005; 

int n, q; 
bool dead[N]; 
int fa[N], sz[N]; 
priority_queue <int, vector <int>, greater <int> > grp[N]; 
int find_fa (int u) { return u == fa[u] ? u : fa[u] = find_fa (fa[u]); }
void union_fa (int u, int v)
{
    u = find_fa (u), v = find_fa (v); 
    if (u != v)
    {
        if (sz[u] < sz[v]) swap (u, v); 
        fa[v] = u; 
        while (!grp[v].empty ()) grp[u].push (grp[v].top ()), grp[v].pop (); 
        sz[u] += sz[v]; 
    }
}
map <int, int> mp; 
signed main ()
{
    read (n); 
    for (int i = 1; i <= n; i ++ ) fa[i] = i, sz[i] = 1; 
    for (int i = 1; i <= n; i ++ )
    {
        int x; read (x); 
        grp[i].push (x); 
        mp[x] = i; 
    }
    read (q); 
    while (q -- )
    {
        char c; int x, y; read (c, x); 
        if (c == 'M')
        {
            read (y); 
            if (dead[x] || dead[y]) continue; 
            union_fa (x, y); 
        }
        else
        {
            if (dead[x]) { write (0, '\n'); continue; }
            x = find_fa (x); 
            int u = grp[x].top (); grp[x].pop (); 
            dead[mp[u]] = 1; 
            write (u, '\n'); 
        }
    }
    return 0; 
}

D. 矩阵

题目描述

有一个 \(n\times m\)的矩阵，初始每个格子的权值都为 \(0\)，可以对矩阵执行两种操作：

1. 选择一行，该行每个格子的权值加 \(1\) 或减 \(1\)。
2. 选择一列，该列每个格子的权值加 \(1\) 或减\(1\)。

现在有 \(K\) 个限制，每个限制为一个三元组 \((x,y,c)\)，代表格子 \((x,y)\) 权值等于\(c\)。
问是否存在一个操作序列，使得操作完后的矩阵满足所有的限制。
如果存在输出 Yes，否则输出 No。

题解

定义横着是加，竖着是减。那么每个限制可以转化为：\(A_x-A_y=c\)（\(A\) 增加量或减少量）
带权并查集维护的是到根节点的距离，那么这个也可以类比到根节点的距离。
\(A_x-A_y=c\) 转化为 \(A_x=A_y+c\)。
那么每次修改的其实就是到根节点的距离。

# include <bits/stdc++.h> 
using namespace std; 
using namespace IOS; 
typedef long long ll; 
//# define int long long 
# define lc u << 1
# define rc u << 1 | 1 
const int N = 2005; 

int n, m, q; 
int fa[N], d[N]; 
int find_fa (int u)
{
    if (u == fa[u]) return u; 
    int v = find_fa (fa[u]); 
    d[u] += d[fa[u]]; 
    return fa[u] = v; 
}
signed main ()
{
    int T; read (T); 
    while (T -- )
    {
        read (n, m, q); 
        for (int i = 1; i <= n + m; i ++ ) fa[i] = i, d[i] = 0; 
        int ans = 1; 
        while (q -- )
        {
            int u, v, w; read (u, v, w); 
            v += n; 
            int fu = find_fa (u), fv = find_fa (v); 
            if (fu != fv)
            {
                fa[fu] = fv; 
                d[fu] = d[v] - d[u] + w; 
            }
            else if (d[u] - d[v] != w) ans = 0; 
		}
		if (ans) puts("Yes");
		else puts("No");
	}
	return 0;
}