codevs 1231_最優(yōu)布線問題_最小生成樹

2019-11-14 09:51:38

字體：大中小

供稿：網(wǎng)友

題目描述

學(xué)校需要將n臺(tái)計(jì)算機(jī)連接起來，不同的2臺(tái)計(jì)算機(jī)之間的連接費(fèi)用可能是不同的。為了節(jié)省費(fèi)用，我們考慮采用間接數(shù)據(jù)傳輸結(jié)束，就是一臺(tái)計(jì)算機(jī)可以間接地通過其他計(jì)算機(jī)實(shí)現(xiàn)和另外一臺(tái)計(jì)算機(jī)連接。

為了使得任意兩臺(tái)計(jì)算機(jī)之間都是連通的（不管是直接還是間接的），需要在若干臺(tái)計(jì)算機(jī)之間用網(wǎng)線直接連接，現(xiàn)在想使得總的連接費(fèi)用最省，讓你編程計(jì)算這個(gè)最小的費(fèi)用。

思路

就是一個(gè)最小生成樹問題，這里因?yàn)閿?shù)據(jù)大，用了并查集+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); } }