poj1985和poj1849（树的直径）

题目传送门：poj1985

树是连通无环图，树上任意两点之间的路径是唯一的。定义树上任意两点u, v的距离为u到v路径上边权的和。树的直径MN为树上最长路径，即点M和N是树上距离最远的两个点。

题目就是寻找树的直径的版子题，两次dfs（第一次遍历根节点所到达的最远距离x点，第二次dfs从x到达最远距离y，这个就是树的直径），或者树形dp，我这里用到了树形dp；

还要感谢石神对我的教导和更正，让我接触了树形dp；

但这个题的代码就不给出了，因为在下面一题的代码中会体现。。

题目：poj1849

所以这里我不仅给出题目的答案，我们也来讨论一下每一种情况；

假设只有1个机器人遍历树,且要求回到原点, 它最少需要走多少路?

2 × ∑wi。

若不用回到原点？

2 × ∑wi−(从出发点所能到达的最远距离)。即沿着最远距离走，过程中每个分叉走两遍。

假设只有2个机器人遍历树,且要求回到原点, 它最少需要走多少路?

2 ×∑wi。

若不用回到原点？

2 ×∑wi−(树的直径)。

这个题就是最后一种情况，

分析：考虑从一个结点遍历整个树再回到原点需要把每个边计算两遍，这里机器人不用回到出发点，所以两个机器人到达的点越远越好。要使路程最近，若起点在树的直径上，则两辆车往不同的方向走，直径上的边只用走一遍，其他的要走两遍。若起点不在直径上，则两人一起走到直径上，再往不同的方向走。这样最优解就是所有边×2−直径，因为直径只走了一次，而其他边必走两遍。

#include<algorithm>

#include<bitset>

#include<cctype>

#include<cerrno>

#include<clocale>

#include<cmath>

#include<complex>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<deque>

#include<exception>

#include<fstream>

#include<functional>

#include<limits>

#include<list>

#include<map>

#include<iomanip>

#include<ios>

#include<iosfwd>

#include<iostream>

#include<istream>

#include<ostream>

#include<queue>

#include<set>

#include<sstream>

#include<stack>

#include<stdexcept>

#include<streambuf>

#include<string>

#include<utility>

#include<vector>

#include<cwchar>

#include<cwctype>

using namespace std;

const int maxn=4e4+;

template<typename T>inline void read(T &x)

{

    x=;

    T f=,ch=getchar();

    while (!isdigit(ch) && ch^'-') ch=getchar();

    if (ch=='-') f=-, ch=getchar();

    while (isdigit(ch)) x=(x<<)+(x<<)+(ch^), ch=getchar();

    x*=f;

}

int n,m,a,b,c,point,tot,ans,sum;

int dis[],vis[],lin[];

struct gg {

    int y,next,v;

}an[];

void add(int x,int y,int z) {

    an[++tot].y=y;

    an[tot].v=z;

    an[tot].next=lin[x];

    lin[x]=tot;

}

inline int dp(int x)

{

    vis[x]=;

    for(int i=lin[x];i;i=an[i].next)

    {

        int y=an[i].y;

        if(vis[y]) continue;

        dp(y);

        ans=max(ans,dis[x]+dis[y]+an[i].v);

        dis[x]=max(dis[x],dis[y]+an[i].v);

    }

    return ans;

}

int main()

{

    int sum=;

    read(n);read(m);

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

    {

        read(a),read(b),read(c);

        add(a,b,c);

        add(b,a,c);

        sum+=c;

    }

    dp();

    printf("%d\n",(sum<<)-ans);

    return ;

}

巴特西

poj1985和poj1849（树的直径）

最新文章

热门文章