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;elsereturn 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; }

?

轉載于:https://www.cnblogs.com/longl/p/9500795.html

總結

以上是生活随笔為你收集整理的牛客小白月赛6 H 挖沟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。