#1097 : 最小生成樹一·Prim算法
時間限制:10000ms
單點時限:1000ms
內存限制:256MB
描述
最近，小Hi很喜歡玩的一款游戲模擬城市開放出了新Mod，在這個Mod中，玩家可以擁有不止一個城市了！

但是，問題也接踵而來——小Hi現在手上擁有N座城市，且已知這N座城市中任意兩座城市之間建造道路所需要的費用，小Hi希望知道，最少花費多少就可以使得任意兩座城市都可以通過所建造的道路互相到達（假設有A、B、C三座城市，只需要在AB之間和BC之間建造道路，那么AC之間也是可以通過這兩條道路連通的）。

提示：不知道為什么Prim算法和Dijstra算法很像呢Σ(っ °Д °;)っ 。
輸入
每個測試點（輸入文件）有且僅有一組測試數據。

在一組測試數據中：

第1行為1個整數N，表示小Hi擁有的城市數量。

接下來的N行，為一個N*N的矩陣A，描述任意兩座城市之間建造道路所需要的費用，其中第i行第j個數為Aij，表示第i座城市和第j座城市之間建造道路所需要的費用。

對于100%的數據，滿足N<=10^3，對于任意i，滿足Aii=0，對于任意i, j滿足Aij=Aji, 0<Aij<10^4.

輸出
對于每組測試數據，輸出1個整數Ans，表示為了使任意兩座城市都可以通過所建造的道路互相到達至少需要的建造費用。

樣例輸入
5
0 1005 6963 392 1182
1005 0 1599 4213 1451
6963 1599 0 9780 2789
392 4213 9780 0 5236
1182 1451 2789 5236 0
樣例輸出
4178
/*
Prim算法的基本思想：
先從所有點中取一個點（一般加入1號點）加入集合v，其他點放入集合w。
從w中，找 w中的點 與 v中的點 連起來的邊中 的權值最小 的那個點（w集合中的點），所找到的那條權值最小的邊為最小生成樹的一條邊，將那個點加入v集合，然后將它清出w集合，重復上述操作，直到w集合為空
*/
AC_code:

#include <bits/stdc++.h> #define LL long long using namespace std; int a[1005][1005]; vector<int>v,w; LL sum ,aim,s,e,pos; LL Prim() {while(!w.empty()){vector<int>::iterator it = w.begin();aim = 0x3f3f3f3f;for(int i = 0; i < v.size(); i++){for(int j = 0; j < w.size(); j++){if(a[v[i]][w[j]] < aim){aim = a[v[i]][w[j]];s = v[i];e = w[j];pos = j;}}}sum += a[s][e];v.push_back(e);w.erase((it+pos));}return sum; } int main() {int N;scanf("%d",&N);v.push_back(1);for(int i = 1; i <= N; i++){for(int j = 1; j <= N; j++){scanf("%d",&a[i][j]);}if(i!=1)w.push_back(i);}printf("%lld\n",Prim());return 0; }

總結

以上是生活随笔為你收集整理的#1097 : 最小生成树一·Prim算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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