国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

codevs 1231_最優布線問題_最小生成樹

2019-11-14 10:49:14
字體：大 中 小
來源：轉載
供稿：網友

題目描述

學校需要將n臺計算機連接起來，不同的2臺計算機之間的連接費用可能是不同的。為了節省費用，我們考慮采用間接數據傳輸結束，就是一臺計算機可以間接地通過其他計算機實現和另外一臺計算機連接。

為了使得任意兩臺計算機之間都是連通的（不管是直接還是間接的），需要在若干臺計算機之間用網線直接連接，現在想使得總的連接費用最省，讓你編程計算這個最小的費用。

思路

就是一個最小生成樹問題，這里因為數據大，用了并查集+kruskal，暴力一下就可以了 O(nlogn)

#include <stdio.h>#include <algorithm>using namespace std;int f[100001];struct arr{ int x,y,z;};arr a[100001];int cam(arr x,arr y){ return x.z<y.z;}int find(int x){ if (!f[x]) return x; f[x]=find(f[x]); return f[x];}int insert(int x,int y){ if (find(x)!=find(y)) { f[find(x)]=find(y); return 1; } return 0;}int main(){ int n,m; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+m+1,cam); long long tot=0; for (int i=1;i<=m;i++) { if (find(a[i].x)!=find(a[i].y)) { tot+=a[i].z; insert(a[i].x,a[i].y); } }

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 新蔡县| 衡东县| 贺州市| 富顺县| 岑巩县| 襄樊市| 台北市| 贵南县| 东乡族自治县| 凤山市| 建平县| 阜新市| 密山市| 陈巴尔虎旗| 东平县| 乌拉特后旗| 宁化县| 兰州市| 方山县| 兴义市| 奉贤区| 堆龙德庆县| 东兴市| 琼中| 宜兴市| 肇州县| 察隅县| 雅安市| 六枝特区| 沽源县| 乌审旗| 吉木乃县| 中西区| 分宜县| 伊吾县| 崇仁县| 徐州市| 河东区| 收藏| 蒙自县| 伊通|