首页 > 其他 > 详细

牛客小白月赛6 H 挖沟

时间:2018-08-19 12:34:48      阅读:210      评论:0      收藏:0      [点我收藏+]

H 挖沟

题目:

链接:https://www.nowcoder.com/acm/contest/136/H
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述


    胡队长带领HA实验的战士们玩真人CS,真人CS的地图由一些据点组成,现在胡队长已经占领了n个据点,为了方便,将他们编号为1-n,为了隐蔽,胡队长命令战士们在每个据点出挖一个坑,让战士们躲在坑里。由于需要在任意两个点之间传递信息,两个坑之间必须挖出至少一条通路,而挖沟是一件很麻烦的差事,所以胡队长希望挖出数量尽可能少的沟,使得任意两个据点之间有至少一条通路,顺便,尽可能的∑d[i][j]使最小(其中d[i][j]为据点i到j的距离)。

输入描述:

第一行有2个正整数n,m,m表示可供挖的沟数。
接下来m行,每行3个数a,b,v,每行描述一条可供挖的沟,该沟可以使a与b连通,长度为v。

输出描述:

输出一行,一个正整数,表示要使得任意两个据点之间有一条通路,至少需要挖长的沟。(数据保证有解)
示例1

输入

复制
2 2
1 2 1
1 2 3

输出

复制
1
示例2

输入

复制
3 3
1 2 3
2 3 4
1 3 5

输出

复制
7

备注:

对于100%的测试数据:
1 ≤ n ≤ 100000
1 ≤ m ≤ 500000
1 ≤ v ≤ 10000

 

思路:

    最小生成树模板题

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+20;
int pre[maxn],n,m;

int find(int x){
    if(pre[x]==x)
        return x;
    else
        return pre[x]=find(pre[x]);
}


struct Node{
    int from,to,cost;
    bool friend operator <(Node a, Node b){
        return a.cost<b.cost;
    }
}tmp;

vector<Node> edge;

void kruskal(){
    sort(edge.begin(),edge.end());
    for(int i=1;i<=n;i++)pre[i] = i;
    ll sum = 0;
    for(int i=0;i<edge.size();i++){
        tmp = edge[i];
        int fx = find(tmp.from),fy = find(tmp.to);
        if(fx!=fy){
            pre[fx] = fy;
            sum+=tmp.cost;
            //printf("c %d\n",tmp.cost);
        }
    }
    printf("%lld\n",sum);

}


int main()
{


    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&tmp.from,&tmp.to,&tmp.cost);
        edge.push_back(tmp);
    }
    kruskal();
    return 0;
}

 

牛客小白月赛6 H 挖沟

原文:https://www.cnblogs.com/longl/p/9500795.html

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