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≤10⁴), 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≤10⁹)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

输入

输出

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)