频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
Hdu 2419 Boring Game (数据结构_并查集)
2012-07-25 09:00:26      个评论      
收藏   我要投稿


题目大意:给定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); 
    } 


作者:woshi250hua
点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构 查集
上一篇: hdu 3709 Balanced Number (DP_数位DP)
下一篇: HDU-2717-Catch That Cow
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站