并查集扩展应用
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\) 个人，每个人都是一个独立的团。最近统计了每个人善良程度。狱卒可以发两种命令：
Merge(i, j)。把 \(i\) 所在的团和j所在的团合并成一个团。如果 \(i, j\) 有一个人是死人，那么就忽略该命令。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\) 或减\(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;
}