P1546 最短網(wǎng)絡(luò) Agri-Net

• • 526通過
  • 959提交
• 題目提供者JOHNKRAM
• 標(biāo)簽圖論貪心USACO
• 難度普及/提高-

提交該題?討論?題解?記錄

最新討論

• 50分C++代碼，求解
• 請(qǐng)指教哪里出現(xiàn)了問題，只有…
• 求解為什么只有40分

題目背景

農(nóng)民約翰被選為他們鎮(zhèn)的鎮(zhèn)長(zhǎng)！他其中一個(gè)競(jìng)選承諾就是在鎮(zhèn)上建立起互聯(lián)網(wǎng)，并連接到所有的農(nóng)場(chǎng)。當(dāng)然，他需要你的幫助。

題目描述

約翰已經(jīng)給他的農(nóng)場(chǎng)安排了一條高速的網(wǎng)絡(luò)線路，他想把這條線路共享給其他農(nóng)場(chǎng)。為了用最小的消費(fèi)，他想鋪設(shè)最短的光纖去連接所有的農(nóng)場(chǎng)。

你將得到一份各農(nóng)場(chǎng)之間連接費(fèi)用的列表，你必須找出能連接所有農(nóng)場(chǎng)并所用光纖最短的方案。每?jī)蓚€(gè)農(nóng)場(chǎng)間的距離不會(huì)超過100000

輸入輸出格式

輸入格式：

?

第一行： 農(nóng)場(chǎng)的個(gè)數(shù)，N（3<=N<=100）。

第二行..結(jié)尾: 后來的行包含了一個(gè)N*N的矩陣,表示每個(gè)農(nóng)場(chǎng)之間的距離。理論上，他們是N行，每行由N個(gè)用空格分隔的數(shù)組成，實(shí)際上，他們限制在80個(gè)字符，因此，某些行會(huì)緊接著另一些行。當(dāng)然，對(duì)角線將會(huì)是0，因?yàn)椴粫?huì)有線路從第i個(gè)農(nóng)場(chǎng)到它本身。

?

輸出格式：

?

只有一個(gè)輸出，其中包含連接到每個(gè)農(nóng)場(chǎng)的光纖的最小長(zhǎng)度。

?

輸入輸出樣例

輸入樣例#1：
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 輸出樣例#1：
28

說明

題目翻譯來自NOCOW。

USACO Training Section 3.1

分析：赤裸裸的最小生成樹，具體思路就是貪心，把邊按權(quán)值排序，枚舉邊，如果邊連接的兩個(gè)點(diǎn)不連通，則連接，直到所有點(diǎn)連通.

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm>using namespace std;int n,fa[1010],tot,sum,cnt; struct node {int x, y, w; }e[100100];bool cmp(node a, node b) {return a.w < b.w; }int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]); }bool check(int x, int y) {if (find(x) != find(y)){fa[find(y)] = find(x);return true;}return false; }int main() {scanf("%d", &n);for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){int temp;scanf("%d", &temp);if (temp){e[++tot].w = temp;e[tot].x = i;e[tot].y = j;}}sort(e + 1, e + tot + 1, cmp);for (int i = 1; i <= n; i++)fa[i] = i;for (int i = 1; i <= tot; i++){if (check(e[i].x, e[i].y)){cnt++;sum += e[i].w;}}printf("%d", sum);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/zbtrs/p/5791320.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P1546 最短网络 Agri-Net的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。