Hdu 2419 Boring Game (数据结构_并查集)

题目大意：给定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)
     &nb

补充：软件开发 , C++ ,