2017 강소성 새 JSPC H (탐욕, prim)

제목 설명
나무 한 그루 를 드 리 겠 습 니 다. 두 노드 사이 에 ci c i 거리 가 있 습 니 다. 지금 지 도 를 재건 하려 고 합 니 다. 임의의 두 정점 간 의 비용 은 그들 사이 의 가장 짧 은 길이 고 최대 생 성 나 무 를 만 드 는 데 비용 이 듭 니 다.
분석 하 다.
이 문 제 는 경 기 를 할 때 풀 지 못 했 습 니 다. 경기 후에 문 제 를 보 는 것 은 매우 간단 합 니 다. prim 의 나무 건설 과정 을 상상 할 때마다 나머지 변 집합 중의 최대 거 리 를 찾 습 니 다. 분명히 우 리 는 먼저 지름 v0, v1 v 0, v 1 을 찾 은 다음 에 나머지 점 을 찍 어야 합 니 다. 나머지 점 에 대해 서 는 v0 까지 추가 하지 않 고 v1 v 0 까지 추가 하지 않 으 면 v 1 까지 추가 하지 않 습 니 다.그 가 임 의 점 까지 의 거 리 는 max (dist (v, v0), dist (v, v1) m a x (d i s t (v, v 0), d i s t (v, v 1) 를 초과 하지 않 는 다 는 것 을 증명 할 수 있 기 때문에 이 결론 은 v0, v1 v 0, v 1 이 지름 이기 때문이다.
AC code

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define pb push_back
#define mp make_pair
#define PI acos(-1)
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
using namespace std;
const int MOD = 1e9+7;
const int MAX_P = 2e4+10;
const int maxn = 1e5+10;
const int MAX_V = 5e5+10;
const double eps = 1e-8;
typedef long long LL;
typedef long double DB;
typedef pair<int,int> Pair;

struct Edge{
    int from,to,cost;
};

Edge E[maxn*2];
int ne;
std::vector<int> G[maxn];
void add_edge(int u,int v,int cost){
    E[ne++] = Edge{u,v,cost};
    G[u].pb(ne-1);
    E[ne++] = Edge{v,u,cost};
    G[v].pb(ne-1);
}

LL d[2][maxn];
bool vis[maxn];
void bfs(int s,LL *dist){
    dist[s] = 0;
    memset(vis,0,sizeof(vis));
    vis[s] = true;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i=0 ; iif(!vis[e.to]){
                dist[e.to] = dist[u] + e.cost;
                vis[e.to] = true;
                Q.push(e.to);
            }
        }
    }
}


int main() {
    int n;
    while (scanf("%d",&n ) != EOF) {
        for(int i=1 ; i<=n ; ++i)G[i].clear();
        ne = 0;
        for(int i=0 ; i1 ; ++i){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c );
            add_edge(a,b,c);
        }
        LL ans =0;
        bfs(1,d[0]);
        int v0 = 1;
        for(int i=1 ; i<=n ; ++i)
            if(d[0][v0] < d[0][i])v0 = i;
        bfs(v0,d[0]);
        int v1 = 1;
        for(int i=1 ; i<=n ; ++i){
            //std::cout << d[0][i] << '
';
            if(d[0][v1] < d[0][i])v1 = i;
        }
        bfs(v1,d[1]);
        ans = d[0][v1];
        for(int i=1 ; i<=n ; ++i){
            //std::cout << d[1][i] << '
';
            if(i != v0 && i != v1){
                ans += max(d[0][i],d[1][i]);
            }
        }
        //std::cout << v0<
        printf("%lld
",ans );
    }


    return 0;
}