并查集
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\)上也有原題，但被評為藍題，我覺得有點虛高，應該算一道綠題
閑話不多說，開始：
這道題要我們求删邊的最小值，不好維護，但我們可以運用補集的思想,那就是求我們加邊的最大值。
但這道題有一個限制，就是我們每個區域隻能有一個壞點。這就讓我們想到了要用并查集來維護。
#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的原因。前兩道的重點在于如何想到用并查集去維護，而這道題沒有任何含金量，非常簡單，代碼很詳細。
#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;
}
#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
後面的等學到圖論再講吧...
![【趨高機器視覺】機器視覺技術原了解析及解決方案[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)