当前位置:首页 > 数据结构 > XTU 1267 Highway

XTU 1267 Highway

Highway

In ICPCCamp there were n towns conveniently numbered with 1,2,,n connected with (n1) roads. The i-th road connecting towns ai and bi has length ci. It is guaranteed that any two cities reach each other using only roads.

Bobo would like to build (n1) highways so that any two towns reach each using only highways. Building a highway between towns x and y costs him δ(x,y) cents, where δ(x,y) is the length of the shortest path between towns x and y using roads.

As Bobo is rich, he would like to find the most expensive way to build the (n1) highways.

Input

The input contains zero or more test cases and is terminated by end-of-file. For each test case:

The first line contains an integer n. The i-th of the following (n1) lines contains three integers aibi and ci.

  • 1n105
  • 1ai,bin
  • 1ci108
  • The number of test cases does not exceed 

    10

    .

Output

For each test case, output an integer which denotes the result.

Sample Input

5
1 2 2
1 3 1
2 4 2
3 5 1
5
1 2 2
1 4 1
3 4 1
4 5 2

Sample Output

19
15


首先给出的图是树 求重建n-1条边后 再次建成的边权和最大 差不多是这个意思

思路 先求出 树上最远的两个点 反正这两个点肯定是叶结点  我用的最短路求的

然后 以这两个点 更新一个信息 就是树上节点距这两个节点的距离 只保存最长的 那再建的图就用这条边 直接拉过去 但是 找出这两个点是不能连边的 再减去

这个想法是推样例推出来的- -  时间复杂度有点高  3500+ms卡过

还有 xtu最好用__int64

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;

#define ll __int64
const int N=100005;

struct p{
    ll to,val;
};

struct pp{
    ll u,dis;
    bool operator < (const pp&r) const{
        return dis>r.dis;
    }
};
vector<p>G[N];
int n,vis[N];
ll dis[N];

int dijkstra(int s)
{
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    priority_queue<pp>q;
    dis[s]=0;
    q.push(pp{s,0});
    int k=1;
    while(!q.empty())
    {
        pp now=q.top();
        q.pop();
        if(vis[now.u]) continue;
        vis[now.u]=1;
        for(int i=0;i<G[now.u].size();i++)
        {
            p t=G[now.u][i];
            if(dis[t.to]>dis[now.u]+t.val)
            {
                dis[t.to]=dis[now.u]+t.val;
                if(dis[k]<dis[t.to])
                    k=t.to;
                q.push(pp{t.to,dis[t.to]});
            }
        }
    }
    return k;
}
void get(int s)
{
    memset(vis,0,sizeof(vis));
    queue<pp>q;
    vis[s]=1;
    q.push(pp{s,0});
    while(!q.empty())
    {
        pp now=q.front();
        q.pop();
        dis[now.u]=max(now.dis,dis[now.u]);
        for(int i=0;i<G[now.u].size();i++)
        {
            p t=G[now.u][i];
            if(!vis[t.to])
            {
                vis[t.to]=1;
                q.push(pp{t.to,now.dis+t.val});
            }
        }
    }
}
int main()
{
    ll u,v,c;
    int k1,k2;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++) G[i].clear();
        for(int i=1;i<n;i++)
        {
            scanf("%I64d %I64d %I64d",&u,&v,&c);
            G[u].push_back(p{v,c});
            G[v].push_back(p{u,c});
        }
        k1=dijkstra(1);
        ll t=dis[k1];
        k2=dijkstra(k1);
        t=max(t,dis[k2]);
        memset(dis,0,sizeof(dis));
        get(k1);get(k2);
        ll ans=0;
        for(int i=1;i<=n;i++)
            ans+=dis[i];
        printf("%I64d\n",ans-t);
    }
    return 0;
}


除特别注明外,本站所有文章均为whppmy原创,转载请注明出处来自http://www.dengwenhuo.cn/?id=453

上一篇:kmp

发表评论

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。