注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

【并查集】hdu 3038 How Many Answers Are Wrong  

2011-12-16 10:07:25|  分类: ACM_并查集 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目链接:
题目大意:
有N个数字,和M个操作,
M个操作分别是给出这N个数字中第A个到第B个的和是C
找出给出的M个操作中有多少个是不合法(和前面的和冲突)的
如果不合法则舍去这个操作,

分析:
刚开到这个题,感觉这个题和ural上的1003挺相似的,1003是并查集,所以这题应该也差不多,
先转化一下,
d[x] 表示数组中[0,x]上的和
那么第A个到第B个的和是C可以表示成
d[B] - d[A-1] = C
都转化为从0开始的和
然后记录一个dis[x]表示x和他的父节点fath[x]的d之差
dis[x] = d[fath[x]] - d[x]
对于每个操作有,
A --;
如果fath[A] == fath[B] ,表示A和B是可比的,所以应该有dis[B] - dis[A] == C,否则不合法

如果fath[A] != fath[B],那么就合并A,B,
令fa = fath[A];
fb = fath[B];
分情况看,让小的节点作为父节点

代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
#define MAXN 200010
#define MAXM 40010
using namespace std;

int n,m;
int fath[MAXN];
int dis[MAXN];
int hash[MAXN];
int hcont;

//disa = fath[a] - a;
//disb = fath[b] - b;
//td = b - a
//fath[b] - fath[a] = b - a + disb - disa =td + disb - disa;

int findset(int x)
{
        int t;
        if(fath[x] != x)
        {
                t = fath[x];
                fath[x] = findset(fath[x]);
                dis[x] += dis[t];//更新到父节点的dis
        }
        return fath[x];
}

void init()
{
        for(int i = 0;i <= n;i ++)
        {
                fath[i] = i;
                dis[i] = 0;
        }
}

void work()
{
        int ta,tb,td;
        int fa,fb;
        int disa,disb;
        int ans = 0;
        for(int i = 0;i < m;i ++)
        {
                scanf("%d%d%d",&ta,&tb,&td);
                ta --;
                fa = findset(ta);
                fb = findset(tb);
                if(fa == fb)
                {
                        disa = dis[ta];
                        disb = dis[tb];
                        if(disb - disa != td)
                                ans ++;
                }
                else
                {
                        if(fa > fb)
                        {
                                dis[fa] = dis[tb] - dis[ta] - td;
                                fath[fa] = fb;
                        }
                        else
                        {
                                dis[fb] = dis[ta] + td - dis[tb];
                                fath[fb] = fa;
                        }
//                        fath[fa] = fb;
//                        dis[fa] += td + dis[tb] - dis[ta];
//刚开始的时候用的是上面注释掉的代码来进行合并操作的,后来总是WA,看网上有人用了上面没有注释的合并的方法AC
//也许是INT溢出导致???
                }
        }
        printf("%d\n",ans);
}

int main()
{
        while(scanf("%d%d",&n,&m) != EOF)
        {
                init();
                work();
        }
        return 0;
}
  评论这张
 
阅读(293)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018