随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:  。
 4 How to Do:    sum[x]表示由第x+1个元素到根元素的元素之和。三个关键点:
 5               1、merge(a-1,b,c);a-1而不是a,因为按我们的思路c=[b+1]-[(a-1)+1]得到的,正好是a~b;
 6               2、sum[px]=sum[y]-sum[x]+c;(注意此处c=元素x+1到元素y的和)
 7               3、路径压缩时的sum[x]的更新。sum[x]+=sum[t].也因此初始化时sum[]=0.
 8   */
 9 #include <cstdio>
10 #include <cstdlib>
11 #define MAXSIZE 200001
12 int n,m;
13 int par[MAXSIZE],sum[MAXSIZE];
14 char ch;
15 
16 int findSet(int x){
17     if(x!=par[x]){
18         int t=par[x];
19         par[x]=findSet(par[x]);
20         sum[x]+=sum[t];
21     }
22     return par[x];
23 }
24 inline bool merge(int x,int y,int c){
25     int px=findSet(x);
26     int py=findSet(y);
27     if(px==py)    return sum[x]-sum[y]==c;
28     par[px]=py;
29     sum[px]=sum[y]-sum[x]+c;
30     return true;
31 }
32 inline void makeSet(int n){
33     int i;
34     for(i=0;i<=n;i++)//从0到n
35         par[i]=i,sum[i]=0;
36 }
37 inline void scan(int &x){
38     while (ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
39     while (ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-'0';
40 }
41 int main(){
42     //freopen("in.txt","r",stdin);
43     while (~scanf("%d%d",&n,&m)){
44         int no=0;
45         makeSet(n);
46         while (m--){
47             int a,b,c;
48             scan(a);
49             scan(b);
50             scan(c);
51             if(!merge(a-1,b,c)) no++;
52         }
53         printf("%d\n",no);
54     }
55     return 0;
56 }
57 
58 
posted on 2012-03-18 15:42 Leo.W 阅读(217) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理