首页 > 试题广场 >

Shortest Path

[编程题]Shortest Path
  • 热度指数:3 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
Today HH becomes a designer, and he faces a problem so he asks you for help.
Treeisland is a country with n cities and n−1 two-way road and from any city you can go to any other cities.
HH the designer is going to design a plan to divide n city into n/2 pairs so that the sum of the length between the n/2 pairs city is minimum.
Now HH has finished it but he doesn't know whether it's true so he ask you to calculate it together.
It's guaranteed that n is even.

输入描述:
The first line contains an positive integer T(1≤T≤100), represents there are T test cases. 
For each test case: The first line contains an positive integer n(1≤n≤104), represents the number of cities in Treeisland, it's guarantee that n is even. 
Then n−1 lines followed. Each line contains three positive integer u, v and len, (u≠v,1≤u≤n,1≤v≤n,1≤len≤109)indicating there is a road of length len between u and v. 
It's guarantee you can get to any city from any city.


输出描述:
For each test case, output in one line an integer, represent the minimum sum of length.
示例1

输入

2
4
1 2 5
2 3 8
3 4 6
6
1 3 5
3 2 3
4 5 4
4 3 9
4 6 10

输出

11
31

说明

In the first example, you can divide them into (1,2), and (3,4), then the minimum sum of length is 5+6=11
In the second example, you can divide them into (1,3),(2,4),(5,6), hen the minimum sum of length is 5+(3+9)+(10+4)=31
 
#include<stdio.h>
#include<vector>
using namespace std;
struct Edge{
    int from,to,dis;
    Edge(int x,int y,int z):from(x),to(y),dis(z){}    
};
vector<Edge> edge;
vector<int> G[10005];
void addEdge(int,int,int);
int cnt[10005];
long long res;
int getCnt(int,int);
void dfs(int,int);
int main(){
    int i,T,n,a,b,c;
    //freopen("input.txt","r",stdin);
    for(scanf("%d",&T);T--;){
        for(i=0;i<10005;i++) G[i].clear();
        edge.clear(),res=0;
        for(scanf("%d",&n),i=0;i<n-1;i++){
            scanf("%d%d%d",&a,&b,&c);
            addEdge(a,b,c),addEdge(b,a,c);
        }
        getCnt(0,1),dfs(0,1);
        printf("%lld\n",res);
    }
}
void addEdge(int from,int to,int dis){
    edge.push_back(Edge(from,to,dis));
    G[from].push_back(edge.size()-1);    
}
int getCnt(int fa,int x){
    int sum=0,i;
    for(i=0;i<G[x].size();i++){
        Edge &e=edge[G[x][i]];
        if(e.to!=fa) sum+=getCnt(x,e.to);
    }
    cnt[x]=sum+1;
    return cnt[x];
}
void dfs(int fa,int x){
    int i;
    for(i=0;i<G[x].size();i++){
        Edge &e=edge[G[x][i]];
        if(e.to==fa) continue;
        if(cnt[e.to]%2) res+=(long long)e.dis;
        dfs(x,e.to);
    }
}

发表于 2017-10-26 17:23:10 回复(0)