首页 > 其他 > 详细

[51Nod] 配对

时间:2018-01-14 15:50:38      阅读:194      评论:0      收藏:0      [点我收藏+]

https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1737

求出树的重心,跑spfa

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>

using namespace std;
const int N = 1e5 + 10;

#define oo 999999999999
#define yxy getchar()

int n, now, Point, Min_siz;
int head[N] ,siz[N], Que[N << 1];
struct Node {int v, w, nxt;} G[N << 1];
bool vis[N];
long long dis[N];

inline int read(){
    int x = 0; char c = yxy;
    while(c < 0 || c > 9) c = yxy;
    while(c >= 0 && c <= 9) x = x * 10 + c - 0, c = yxy;
    return x;
}

inline void add(int u, int v, int w){
    G[now].v = v; G[now].w = w; G[now].nxt = head[u]; head[u] = now ++;
}

void dfs(int u, int father){
    siz[u] = 1;
    int Max_son = -1;
    for(int i = head[u]; ~ i; i = G[i].nxt){
        int v = G[i].v;
        if(v != father){
            dfs(v, u);
            siz[u] += siz[v];
            Max_son = max(Max_son, siz[v]);
        }
    }
    Max_son = max(Max_son, n - siz[u]);
    if(Max_son < Min_siz){
        Min_siz = Max_son;
        Point = u;
    }
}

void spfa(int S){
    for(int i = 1; i <= n; i ++) dis[i] = oo;
    dis[S] = 0;
    int H = 1, T = 1;
    Que[H] = S;
    while(H <= T){
        int topp = Que[H ++];
        vis[topp] = 0;
        for(int i = head[topp]; ~ i; i = G[i].nxt){
            int v = G[i].v;
            if(dis[v] > dis[topp] + G[i].w){
                dis[v] = dis[topp] + G[i].w;
                if(!vis[v]) vis[v] = 1, Que[++ T] = v;
            }
        }
    }
}

int main()
{
    n = read();
    for(int i = 1; i <= n; i ++) head[i] = -1;
    for(int i = 1; i < n; i ++) {
        int u = read(), v = read(), w = read();
        add(u, v, w); add(v, u, w);
    }
    Min_siz = 999999999;
    dfs(1, 0);
    spfa(Point);
    long long Answer = 0;
    for(int i = 1; i <= n; i ++) Answer += dis[i];
    cout << Answer;
    return 0;
}

 

[51Nod] 配对

原文:https://www.cnblogs.com/shandongs1/p/8283411.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!