洛谷1131 [ZJOI2007]时态同步

Luogu

算法

很明显是一道树形DP。

先设$f[i]$表示以i为根的树的最大时间,Dfs统计一下。

然后再来一遍Dfs,算出答案:

$ans+=f[now]-f[v]-e[i].w$

即统计now的最大减now的某子节点的最大再减掉通过时间。

细节见代码。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
typedef long long LL;
struct Edge //邻接表
{
    int v,w,nxt;
    Edge() { this->v=this->w=this->nxt=0; }
}e[1000010];
int head[500010],cnt=0;
bool vis[500010]; //访问标记
int f[500010]; //f[i]表示以i为根的子树的时间的最大值
LL ans=0;
inline void addEdge(int u,int v,int w) //添加无向边
{
    cnt++;
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=head[u];
    head[u]=cnt;
    cnt++;
    e[cnt].v=u;
    e[cnt].w=w;
    e[cnt].nxt=head[v];
    head[v]=cnt;
}
inline void Dfs(int now) //计算子树最大值
{
    vis[now]=true;
    for (re int i=head[now];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!vis[v]) { //没到过
            Dfs(v); //搜
            f[now]=max(f[now],f[v]+e[i].w); //更新最大值
        }
    }
}
inline void Search_Ans(int now) //找答案
{
    vis[now]=true;
    for (re int i=head[now];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!vis[v]) { //同上
            Search_Ans(v);
            ans+=(f[now]-f[v]-e[i].w); //累加答案
        }
    }
}
int main()
{
    int n,s; scanf("%d%d",&n,&s);
    for (re int i=1;i<n;i++) { //输入建图
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
    }
    Dfs(s); memset(vis,false,sizeof(vis)); Search_Ans(s); //Dfs+清空访问标记+找答案
    printf("%lld\n",ans); //输出,注意long long
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 28 PM

发表评论