1?思路

題目鏈接。
最小生成樹（MST）問題。

2?代碼

代碼來自宇宙吾心博客。

#include <iostream> #include <limits> #include <cstring> using namespace std; const int N=2001;char c[N][8]; // 保存字符串 int m[N][N]; // m[i][j]第i個結(jié)點與第j個結(jié)果之間權值 int d[N]; // 遍歷時存儲最小值 bool v[N]; // 遍歷時存儲結(jié)點是否被訪問過 int n;// 比較字符串返回路徑權值 int cmp(int a, int b){int n = 0;for(int i=0; i<7; i++)if(c[a][i] != c[b][i])n ++;return n; } //Prim算法 void prim(){int i, j;for(i=1; i<=n; i++) // 把第1個結(jié)點所有鄰結(jié)點的路徑保存在d中 d[i] = m[1][i];memset(v, 0, sizeof(v));int ans=0;while(1){int mark = -1;int min = numeric_limits<int>::max();for(i=1; i<=n; i++)if(!v[i] && min>d[i]){ // 找到最短的路徑，結(jié)點保存在mark中，權值保存在min中 min = d[i]; mark = i;}if(mark == -1){ // mark==-1表明經(jīng)歷上面的for循環(huán)后mark沒有變化，說明所有的結(jié)點都已經(jīng)訪問過（v中標記也所有的結(jié)點） cout<<"The highest possible quality is 1/"<<ans<<"."<<endl;return;}v[mark] = 1;ans += min;for(i=1; i<=n; i++) if(v[i]==0 && d[i]>m[mark][i])d[i] = m[mark][i];} } // read void read(){int i, j;while(cin>>n){if(!n) return;for(i=1; i<=n; i++)cin>>c[i];for(i=1; i<=n; i++)for(j=i+1; j<=n; j++){m[i][j] = cmp(i, j); // 保存權值 m[j][i] = m[i][j];}prim();} } int main(int argc, char *argv[]) {read();return 0; }

Author: visaya fan?<visayafan[AT]gmail.com>

Date: 2011-08-24 12:55:48

HTML generated by org-mode 6.33x in emacs 23

轉(zhuǎn)載于:https://www.cnblogs.com/visayafan/archive/2011/09/27/2193619.html

總結(jié)

以上是生活随笔為你收集整理的【POJ】【最小生成树】1789 Truck History的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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