題目大意：給定n個點m條邊的無向圖，每個點有點權。有q個操作，每個操作有三種：1、查詢和某個點連通的大於k的最小點權 2、將某點的點權更新為k 3、刪除某條邊。
解題思路：08年網絡賽的題目，全場5個人過，但絕對是難度中等的並查集好題。從這題我學到了對給定操作序列問題的一種很有效的處理方法--逆序處理，還學會STL裡set的幾個操作，收獲頗豐啊。
我們先不想其他的，考慮這個問題的三種操作要我們做什麼。第一種操作就是找某個連通分量的大於k的最小點權，第二種和第三種如果是暴力q*n求解，那麼就自然而然地模擬。
但是復雜度太高了，q為30萬，n為2萬，最多操作60億次。因為有牽扯到連通分量，考慮用並查集做。那麼第一個操作就是要找某個根所有兒子中權值大於k的最小值，著好像和我們平時做的並查集不一樣，平時都是利用根的信息，這就是本題的一個亮點。第二個操作似乎要先找到根再來遍歷兒子，再來更新點權，第三個操作似乎要將某個集合拆成兩個集合。
這些操作如果正序來做，的確很嚇人，第一個我們可以通過STL的set來應付，set的lower_bound方法不就是題目描述的這功能嗎？第三個操作要拆集合很困難，但我們逆序轉換成合並集合，則要簡單、飄逸許多，也不影響結果。這就是本題的兩個亮點。
分析差不多就這樣，接著就是代碼實現，我第一次用set操作，參看了百度和某神牛的代碼，效率還不錯，256ms，排名第三。
測試數據：
3 3 8
4 5 8
1 2
2 3
1 3
F 1 4
E 1 3
F 2 7
E 2 3
E 1 2
F 2 7
U 3 6
F 3 3
out: Case XX: 4.500
1 0 1
0
F 1 0
out: Case XX: 0.00
3 3 8
8 8 8
1 2
2 3
1 3
F 1 9
F 1 8
E 1 3
E 2 3
E 1 2
F 1 8
U 3 6
F 3 7
out: Case XX: 4.000
3 3 9
8 8 8
1 2
2 3
1 3
F 1 9
F 1 8
U 1 5
E 2 3
E 1 2
E 1 3
F 1 5
U 1 6
F 1 6
out:Case XX: 4.750
3 3 11
8 8 8
1 2
2 3
1 3
F 1 9
F 1 8
U 1 5
F 1 6
E 2 3
E 1 2
E 1 3
U 1 4
F 1 5
U 1 6
F 1 6
out: Case XX: 4.400
C艹代碼：
[cpp]
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <set>
#include <algorithm>
using namespace std;
#define MAX 20010
#define PAIR pair<int,int>
struct Query {
char ope[3];
int x,y;
}query[300010];
double ans;
int cost[MAX]; //cost[i]表示每個點的權值
int n,m,q,time,fa[MAX]; //fa[i]表示i屬於哪個集合
multiset<int> map[MAX]; //存放圖，本題將無向圖轉換為有向圖，因為只要判是否連通
multiset<int> ver[MAX]; //存放以某點為父親的所有節點
int GetPa(int x) { //獲取x點的父親，並進行路徑壓縮
int p = x,tp;
while (p != fa[p]) p = fa[p];
while (x != p) {
tp = fa[x];
fa[x] = p,x = tp;
}
return p;
}
void UnionSet(int x,int y) { //將y屬於的集合和x屬於的集合合並
int px = GetPa(x);
int py = GetPa(y);
if (px == py) return;
if (px > py) swap(px,py);
fa[px] = py;
multiset<int>::iterator it;
for (it = ver[px].begin(); it != ver[px].end(); ++it)
ver[py].insert(*it); //合並時子節點也需要合並
}
int main()
{
int i,j,k,cas = 0,a,b,pa;
while (scanf("%d%d%d",&n,&m,&q) != EOF) {
for (i = 1; i <= n; ++i) {
fa[i] = i;
map[i].clear();
ver[i].clear();
scanf("%d",&cost[i]);
}
for (i = 1; i <= m; ++i) {
scanf("%d%d",&a,&b); //邊從小點連到大點
if (a < b) map[a].insert(b);
else map[b].insert(a);
}
for (i = 1; i <= q; ++i) { //先處理所有操作，再往回查詢，加邊
scanf("%s %d%d",query[i].ope,&a,&b);
query[i].x = a,query[i].y = b;
if (query[i].ope[0] == 'U') {
//保存原來的點權，並更新點權
query[i].y = cost[a];
cost[a] = b;
}
else if (query[i].ope[0] == 'E') {
//先刪除這條邊，後面再添加，這樣不需要拆集合
if (a < b) map[a].erase(map[a].find(b));
else map[b].erase(map[b].find(a));
}
}
for (i = 1; i <= n; ++i)
ver[i].insert(cost[i]);
multiset<int>::iterator it;
for (i = 1; i <= n; ++i) //用處理完的圖建立並查集
for (it = map[i].begin(); it != map[i].end(); ++it)
UnionSet(i,*it);
ans = time = 0;
for (i = q; i >= 1; --i) {
a = query[i].x,b = query[i].y;
if (query[i].ope[0] == 'F') {
time++,pa = GetPa(a);
it = ver[pa].lower_bound(b);//set的這個方法很好地應付查詢操作
if (it != ver[pa].end()) ans += *it;
}
else if (query[i].ope[0] == 'U') {
//更新回去
pa = GetPa(a);
it = ver[pa].find(cost[a]);
ver[pa].erase(it);
ver[pa].insert(b);
cost[a] = b;
} www.2cto.com
else UnionSet(a,b); //這一步是逆序處理的關鍵益處，變得異常簡單
}
printf("Case %d: %.3lf\n",++cas,ans/time);
}
}
