首页 > > 程序设计 > C/C++ >

Building Forest CodeForces - 195E

2018-06-17 21:46:33来源：未知阅读 ()

这题意真是难懂啊...话说"An oriented weighted forest is an acyclic weighted digraph in which from each vertex at most one edge goes."这句话到底什么意思...

题意：有n个点要按照1-n的顺序依次插入一个带边权的森林（森林一开始没有任何点、边），第i+1行描述第i个点插入后的操作。如果某一行为(k, v₁, x₁, v₂, x₂, ... , v_k, x_k)，那么k表示要连的边的数量，(vj,xj)表示要从第vj个点连一条边到i，其权值为vj到其原来所在树的根节点的路径总长加上xj。（保证数据不产生重边）

做法：看懂了题，就会发现这是一个非常正常（shui）的加权并查集。

 1 #include<cstdio>
 2 #define md 1000000007
 3 typedef long long LL;
 4 LL fa[100100];
 5 LL hei[100100];//记录点i到父亲节点的路径总长
 6 LL ans,n;
 7 LL find(LL x)
 8 {
 9     if(fa[x]==x)    return x;
10     LL t=find(fa[x]);
11     hei[x]=(hei[fa[x]]+hei[x])%md;
12     fa[x]=t;
13     return fa[x];
14 }
15 int main()
16 {
17     LL i,j,k,v,x,f1;
18     scanf("%I64d",&n);
19     for(i=1;i<=n;i++)
20         fa[i]=i;
21     for(i=1;i<=n;i++)
22     {
23         scanf("%I64d",&k);
24         for(j=1;j<=k;j++)
25         {
26             scanf("%I64d%I64d",&v,&x);
27             f1=find(v);
28             //if(f1==i)    continue;
29             fa[f1]=i;
30             hei[f1]=(x+hei[v])%md;
31             ans=(ans+hei[f1])%md;
32         }
33     }
34     printf("%I64d",(ans+md)%md);
35     return 0;
36 }

曾经犯过的错：

1.答案未取模，输出了负数（写了两次，错了两次）

2.误区：12行

 1 #include<cstdio>
 2 #define md 1000000007
 3 typedef long long LL;
 4 LL fa[100100];
 5 LL hei2[100100];//记录点i连向其父亲节点的边的权值
 6 LL hei[100100];//记录点i到父亲节点的路径总长
 7 LL ans,n;
 8 LL find(LL x)
 9 {
10     if(fa[x]==x)    return x;
11     LL t=find(fa[x]);
12     hei[x]=(hei[fa[x]]+hei2[x])%md;
13     fa[x]=t;
14     return fa[x];
15 }
16 int main()
17 {
18     LL i,j,k,v,x,f1;
19     scanf("%I64d",&n);
20     for(i=1;i<=n;i++)
21         fa[i]=i;
22     for(i=1;i<=n;i++)
23     {
24         scanf("%I64d",&k);
25         for(j=1;j<=k;j++)
26         {
27             scanf("%I64d%I64d",&v,&x);
28             f1=find(v);
29             if(f1==i)    continue;
30             fa[f1]=i;
31             hei2[f1]=(x+hei[v])%md;
32         }
33     }
34     for(i=1;i<=n;i++)
35         ans=(ans+hei2[i]+md)%md;
36     printf("%I64d",ans);
37     return 0;
38 }