题目地址 题意：给你一个图，每个节点有一个权重，你有3个操作：
U x y 把节点x的权重换为y E x y 把x到y的边删除 F x y 查找与x节点联通的联通块中权重比y大的最小的权重
思路：看到联通块就想到了用并查集去维护最方便，但是因为有删边的操作，这样的话普通的并查集就很难维护了，所以我们可以把过程反向，从后往前维护，这样的话删边就变成合并了，这样的话就比较好维护了。所以说我们先把连起来的边记录下来，对删除操作就先把操作反向，然后把这条边从边集删除掉，最后得到的边集就用来建立并查集就好了。然后每次和并把较小的数集合并到较大的数集就好了，然后查找的时候就是在这个联通块的根节点进行二分查找就好了。
#include <iostream> #include <cstring> #include <string> #include <queue> #include <vector> #include <map> #include <set> #include <stack> #include <cmath> #include <cstdio> #include <algorithm> #include <iomanip> #define N 20010 #define M 60010 #define Q 300010 #define LL __int64 #define inf 0x3f3f3f3f #define lson l,mid,ans<<1 #define rson mid+1,r,ans<<1|1 #define getMid (l+r)>>1 #define movel ans<<1 #define mover ans<<1|1 using namespace std; const LL mod = 1000000007; int nums[N]; struct node { char u; int x, y; }wt[Q]; int pre[N]; multiset<int>mapp[N]; multiset<int>num[N]; multiset<int>::iterator it; int n, m, q; void init() { for (int i = 0; i <= n; i++) { mapp[i].clear(); num[i].clear(); pre[i] = i; } } int find(int x) { if (x == pre[x]) { return x; } return pre[x] = find(pre[x]); } void Union(int x, int y) { int xx = find(x); int yy = find(y); if (xx != yy) { if (num[xx].size()>num[yy].size()) {//减少加入时间 swap(xx, yy); } pre[xx] = yy; for (multiset<int>::iterator its = num[xx].begin(); its != num[xx].end(); its++) { num[yy].insert(*its); } } } int main() { int a, b; int Case = 1; while (~scanf("%d %d %d", &n, &m, &q)) { for (int i = 1; i <= n; i++) { scanf("%d", &nums[i]); } init(); for (int i = 0; i<m; i++) { scanf("%d %d", &a, &b); mapp[min(a, b)].insert(max(a, b)); } for (int i = 0; i<q; i++) { scanf(" %c %d %d", &wt[i].u, &wt[i].x, &wt[i].y); if (wt[i].u == 'U') { swap(nums[wt[i].x], wt[i].y); } else if (wt[i].u == 'E') { if (wt[i].x>wt[i].y) { swap(wt[i].x, wt[i].y); } mapp[wt[i].x].erase(mapp[wt[i].x].find(wt[i].y)); } } for (int i = 1; i <= n; i++) { num[i].insert(nums[i]); } for (int i = 1; i <= n; i++) { for (it = mapp[i].begin(); it != mapp[i].end(); it++) { Union(i, *it); } } int cnt = 0; double ans = 0; for (int i = q - 1; i >= 0; i--) { if (wt[i].u == 'U') { int x = find(wt[i].x); it = num[x].find(nums[wt[i].x]); num[x].erase(it); num[x].insert(wt[i].y); nums[wt[i].x] = wt[i].y; } else if (wt[i].u == 'E') { Union(wt[i].x, wt[i].y); } else { cnt++; int x = find(wt[i].x); it = num[x].lower_bound(wt[i].y); if (it != num[x].end()) { ans += (*it); } } } printf("Case %d: %.3lf\n", Case++, ans / cnt); } return 0; }