Building Forest CodeForces

Building Forest CodeForces - 195E

这题意真是难懂啊...话说"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）的加权并查集。

 #include<cstdio>

 #define md 1000000007

 typedef long long LL;

 LL fa[];

 LL hei[];//记录点i到父亲节点的路径总长

 LL ans,n;

 LL find(LL x)

 {

     if(fa[x]==x)    return x;

     LL t=find(fa[x]);

     hei[x]=(hei[fa[x]]+hei[x])%md;

     fa[x]=t;

     return fa[x];

 }

 int main()

 {

     LL i,j,k,v,x,f1;

     scanf("%I64d",&n);

     for(i=;i<=n;i++)

         fa[i]=i;

     for(i=;i<=n;i++)

     {

         scanf("%I64d",&k);

         for(j=;j<=k;j++)

         {

             scanf("%I64d%I64d",&v,&x);

             f1=find(v);

             //if(f1==i)    continue;

             fa[f1]=i;

             hei[f1]=(x+hei[v])%md;

             ans=(ans+hei[f1])%md;

         }

     }

     printf("%I64d",(ans+md)%md);

     return ;

 }

曾经犯过的错：

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

2.误区：12行

 #include<cstdio>

 #define md 1000000007

 typedef long long LL;

 LL fa[];

 LL hei2[];//记录点i连向其父亲节点的边的权值

 LL hei[];//记录点i到父亲节点的路径总长

 LL ans,n;

 LL find(LL x)

 {

     if(fa[x]==x)    return x;

     LL t=find(fa[x]);

     hei[x]=(hei[fa[x]]+hei2[x])%md;

     fa[x]=t;

     return fa[x];

 }

 int main()

 {

     LL i,j,k,v,x,f1;

     scanf("%I64d",&n);

     for(i=;i<=n;i++)

         fa[i]=i;

     for(i=;i<=n;i++)

     {

         scanf("%I64d",&k);

         for(j=;j<=k;j++)

         {

             scanf("%I64d%I64d",&v,&x);

             f1=find(v);

             if(f1==i)    continue;

             fa[f1]=i;

             hei2[f1]=(x+hei[v])%md;

         }

     }

     for(i=;i<=n;i++)

         ans=(ans+hei2[i]+md)%md;

     printf("%I64d",ans);

     return ;

 }

巴特西

Building Forest CodeForces - 195E

最新文章

热门文章