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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【BZOJ1060】【ZJOI2007】【时态同步】  

2014-03-19 16:06:26|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
     题目大意:该乃一棵边权树和树上一个点,然后要求给某些边增加边权使得该点到各个叶子的距离都相等,问最小需要增加多少点权。
     首先要求该根到各叶子节点的距离相同,实际上也就是要求它的子树到各个叶子节点相同,而当咱们保证了某棵子树的根到叶子节点的距离相同的时候,咱们实际上可以把这个看做一条链了,所以这就可以看做一个树形DP了...递归处理子树的然后再处理父亲,这种贪心的做法是最优的么?可以调整一下嘛,假设某某一个边的修改值变小,那么它显然就需要下传那个差额给其他子树,而子树的个数>=1,所以肯定不会比这个方法优。
    业界良心....所以就用c++写下吧....
    成功模拟了原标程的数据溢出...然后交到BZOJ却WA了233233233(咱不知道为什么!)。
    咱只能说以下的程序对于原ZJ数据是对的,BZOJ WA了不知道怎么回事....要想变成真正的正确的程序改一下一些数据范围即可。
=======================================

#include <cstdio>
#include <cstring>
#include <cstdlib>
#define maxn 500010
using namespace std;

struct edge{
       int u,v,pre,w;
       }e[maxn*2];
       
int n,root,tot=0,last[maxn],f[maxn],que[maxn],len[maxn];
long long ans;

void addedge(int u,int v,int w)
{
     e[++tot].u=u;e[tot].v=v;e[tot].w=w;e[tot].pre=last[u];last[u]=tot;
     e[++tot].u=v;e[tot].v=u;e[tot].w=w;e[tot].pre=last[v];last[v]=tot;
}

void init()
{
     int u,v,w;
     memset(f,0,sizeof(f));
     memset(len,0,sizeof(len));
     memset(last,0,sizeof(last));
     scanf("%d",&n);
     scanf("%d",&root);
     for (int i=1;i<n;i++) 
     {
         scanf("%d%d%d",&u,&v,&w);
         addedge(u,v,w);
     }
     f[root]=0;
     ans=0;
}

void bfs()
{
     memset(que,0,sizeof(que));
     int l=0,r=1,tmp;
     que[l]=root;
     while (l<r)
     {
           int u=que[l++];
           tmp=last[u];
           while (tmp)
           {
                 if (f[u]!=e[tmp].v)
                 {
                                    f[e[tmp].v]=u;
                                    que[r++]=e[tmp].v;
                 }
                 tmp=e[tmp].pre;
           }
     }
     l--;
     for (int i=l;i>=0;i--)
     {
         int p=que[i];
         tmp=last[p]; 
         while (tmp)
         {
               
                if (f[p]!=e[tmp].v)
                {
                             if (len[e[tmp].v]+e[tmp].w>len[p]) 
                             len[p]=len[e[tmp].v]+e[tmp].w;
                }
                tmp=e[tmp].pre;
         }
         tmp=last[p];
         while (tmp)
         {  
              if (f[p]!=e[tmp].v) ans+=len[p]-len[e[tmp].v]-e[tmp].w;
              tmp=e[tmp].pre;
         }
     }
}

int main()
{
    init();
    bfs();
    printf("%I64d",ans);
    return 0;
}
     

  评论这张
 
阅读(118)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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