并查集
E. 【例题4】超市购物 - 「图论」第1章 并查集课堂过关 - 高效进阶 - 课程 - YbtOJ
又是一道并查集好题，我一开始没有看出来为什么要用并查集，我不会告诉你我是看了别人的博客才会的。用并查集维护时间，如果我们的时间到达了0，那我们就不能再进入操作了接下来看代码解决。
code:
#include <bits/stdc++.h>
//#define int long long
using namespace std;
inline int read(){
int x=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return w*x;
}
int n;
struct node{
int v,t;
}a[10004];
int fa[10004];
bool cmp(node a,node b){
return a.v>b.v;
}
int find(int x){
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
int ans;
int main(){
n=read();
for(int i=1;i<=n;i++)
a[i].v=read(),a[i].t=read();
for(int i=1;i<=10001;i++) //这里一定要为10001，不要设成n，因为时间可以比n大(不会告诉你，我锅了很长时间)
fa[i]=i;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
int t=find(a[i].t);
if(t)
{
ans+=a[i].v;
fa[t]=t-1;
}
}
cout<<ans<<endl;
return 0;
}
F. 【例题5】逐个击破 - 「图论」第1章 并查集课堂过关 - 高效进阶 - 课程 - YbtOJ
这道题在\(luogu\)上也有原题，但被评为蓝题，我觉得有点虚高，应该算一道绿题
闲话不多说，开始：
这道题要我们求删边的最小值，不好维护，但我们可以运用补集的思想,那就是求我们加边的最大值。
但这道题有一个限制，就是我们每个区域只能有一个坏点。这就让我们想到了要用并查集来维护。
code:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n, m;
long long ans;
int vis[100010], fa[100010];
struct arr {
int u, v, w;
} e[100010];
inline int read() {
int x = 0, w = 1;
char ch = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '0')
w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + (ch - 48), ch = getchar();
return x * w;
}
int gf(int x) { return x == fa[x] ? x : fa[x] = gf(fa[x]); }
inline int cmp(arr a, arr b) { return a.w > b.w; }
int main() {
// freopen("shiitake.in","r",stdin);
// freopen("shiitake.out","w",stdout);
n = read();
m = read();
for (int i = 1; i <= m; i++) {
int x = read();
vis[x] = 1;
}
for (int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
e[i].u = u;
e[i].v = v;
e[i].w = w;
ans += w;
}
sort(e + 1, e + n, cmp);
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 1; i < n; i++) {
int f1 = gf(e[i].u);
int f2 = gf(e[i].v);
if (!(vis[f1] && vis[f2])) {
fa[f2] = f1;
vis[f1] = (vis[f1] || vis[f2]);
ans -= e[i].w;
}
}
printf("%lld\n", ans);
}
A. 1.躲避拥挤 - 「图论」第1章 并查集强化训练 - 高效进阶 - 课程 - YbtOJ
躲避拥挤的这道题我觉得要比前面的两道题都要简单，可能是T1的原因。前两道的重点在于如何想到用并查集去维护，而这道题没有任何含金量，非常简单，代码很详细。
code:
#include <bits/stdc++.h>
using namespace std;
int test, Q, n, m, tot; // test是数据的组数，Q是每组数据中的询问次数，n是景点数，m是边数
int fa[100001]; //记录其祖先元素
int sum[100001]; //用于维护集合的大小
int ans[100001]; //储存每次询问的答案
struct no //记录原始数据
{
int x; //出发景点
int y; //到达景点
int d; //人气值
} a[100001];
struct de //记录询问的数据
{
int x; //记录要求不能超过的人气值的大小
int num; //记录第几次询问
} q[100001];
bool cmp1(no a, no b) //将原始数据按从小到大的顺序排个序
{
return a.d < b.d;
}
bool cmp2(de a, de b) //将询问数据也按从小到大的顺序排个序
{
return a.x < b.x;
}
int find(int x) //并查集基本操作，寻找该节点的祖先
{
if (!fa[x]) {
return x;
}
return fa[x] = find(fa[x]);
}
void add(int x, int y) //并查集基本操作，合并两个集合，不过要穿差一点东西，以到达维护sum数组的目的
{
int u = find(x); //寻找x祖先元素
int v = find(y); //寻找y祖先元素
if (u == v) //如果两个元素已在同一个集合，则直接忽略
{
return;
}
tot += sum[u] * sum[v] * 2; //否则，这两个点对答案的贡献就是sum[u]*sum[v]*2（不要忘记乘2）
fa[u] = v; //合并两个集合
sum[v] += sum[u]; //维护sum数组
}
int main() {
scanf("%d", &test); //输入test
while (test--) // test次循环
{
scanf("%d%d%d", &n, &m, &Q); //读入
for (int i = 1; i <= m; i++) //读入
{
scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].d);
}
sort(a + 1, a + m + 1, cmp1); //给原始数据排序
for (int i = 1; i <= Q; i++) //读入
{
scanf("%d", &q[i].x); //读入
q[i].num = i; //记录一下是第几次询问
}
sort(q + 1, q + 1 + Q, cmp2); //给询问数据排序
tot = 0; //记录景点的对数
for (int i = 1; i <= n; i++) //并查集基本操作之一————初始化
{
fa[i] = 0;
sum[i] = 1; //初始时每个元素都是一个集合，所以sum数组的值都为1
}
int j = 1; //记录当前询问到第几组道路
for (int i = 1; i <= Q; i++) {
while ((j <= m) && (a[j].d <= q[i].x)) {
add(a[j].x, a[j].y); //合并两个集合
j++; //询问数加1
}
ans[q[i].num] = tot; //记录答案
}
for (int i = 1; i <= Q; i++) //输出
{
printf("%d\n", ans[i]);
}
}
return 0; //完结撒花
}
B. 3.数列询问 - 「图论」第1章 并查集强化训练 - 高效进阶 - 课程 - YbtOJ
自认为这道题要用到数学的一些知识，这道题的问法太并查集了，所以我们知道要用并查集做。
用\(b_i\)表示数组\(a\)的前缀和。发现每一组询问\(l,r,k\)就表示
\[b_r-b_{l-1}=k(mod\ p) \]我们可以用并查集来维护该关系，并查集中每一条边维护该点和父亲差对\(p\)取模的结果。
如果点\(l-1\)和点\(r\)不在一个并查集，那就将两者放入一个并查集中并设置边权。
如果\(l-1\)和点\(r\)在一个并查集，那就判断两者之间是否合法。
时间复杂度是\(O(n×α(n))\)。
C. 4.染色操作 - 「图论」第1章 并查集强化训练 - 高效进阶 - 课程 - YbtOJ（********************）
这道题很有个性，他考的是区间中的东西，区间一定要想到几个点，分别是DP，线段树，ST表，树状数组(我不会)，这道题确实用线段树可做，但只能拿到60分(但我觉得某些大佬一定会用卡常技巧,A掉的)。这道题我们用巧妙的并查集，我们枚举每个区间的点，这样就行了，因为每个点最多被访问一次，所以不会T掉。
Tcode:
这份代码被T掉了，但是更好理解
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
const int maxn = 2e6 + 3;
int fa[maxn];
int n, m;
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void init() {
for (int i = 0; i <= n; i++) {
fa[i] = i;
}
}
int main() {
while (~scanf("%d%d", &n, &m)) {
init();
for (int i = 0; i < m; i++) {
int x, y;
scanf("%d%d", &x, &y);
while (find(y) != find(x - 1)) {
fa[find(y)] = fa[find(y) - 1];
n--;
}
cout << n << endl;
}
}
return 0;
}
code:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 40;
int fa[maxn], n, m, l, r;
int Find(int x) {
if (fa[x] == x)
return x;
return fa[x] = Find(fa[x]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n + 1; i++) fa[i] = i;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &l, &r);
if (l > r)
swap(l, r);
while (1) {
l = Find(l);
if (l > r)
break;
else {
n--;
fa[l] = l + 1;
}
}
printf("%d\n", n);
}
return 0;
}
D. 5.小明反击 - 「图论」第1章 并查集强化训练 - 高效进阶 - 课程 - YbtOJ
后面的等学到图论再讲吧...