【wikioi】1003 電話連線

​​題目連結​​

算法： 最小生成樹

PS：被卡過2天（中間的時間沒去做）。日期：2013-09-13 13:49:47 ~ 2013-09-17 13:01:07

此題為基礎題

剛開始學圖論時隻會用Kruskal+并查集，以為Kruskal和Prim差不多= =于是就用Kruskal來做這題，結果是不用說的

然後就學習了Prim，并在我之前的博文有介紹 最小生成樹

題目描述：

       一個國家有n個城市。若幹個城市之間有電話線連接配接，現在要增加m條電話線（電話線當然是雙向的了），使得任意兩個城市之間都直接或間接經過其他城市有電話線連接配接，你的程式應該能夠找出最小費用及其一種連接配接方案。

需要注意的是，輸入中可能已經包含了電話線，是以要判斷此電話線是否存在（輸入中0表示有，故判斷是否為true即可），存在就不予考慮。不會影響到算法。

CODE：

//最小生成樹 Prim算法 //我沒用到優先隊列，是直接用暴力找出的= = #include <iostream> #include <algorithm> using namespace std; const int MAXN = 105; const int INF = 2147483647; int i, j, n; long long ans = 0; int edge[MAXN][MAXN], key[MAXN], p[MAXN], vis[MAXN] = {0}, //edge表示存的邊 key表示權值，p表示父親，vis表示是否已經存在已生成的樹中  f[MAXN], l[MAXN], m = 0; //f表示頭，右邊表示尾 int main() {  cin >> n;  for(i = 1; i <= n; i++)for(j = 1; j <= n; j++) cin >> edge[i][j];  for(i = 1; i <= n; i++) key[i] = INF;  key[1] = 0; //  p[1] = 1;  int Mini, Min;  for(i = 0; i < n; i++) //之需要加最多n條邊，故循環n次  {   Min = INF;   for(j = 1; j <= n; j++) if(!vis[j] && key[j] < Min){Mini = j; Min = key[j];} //找key值最小的點，即與樹相鄰的節點的最小權值邊   vis[Mini] = 1; //設定通路過，即生成樹已連接配接Mini這個節點   ans += key[Mini];    if(key[Mini])   {    f[m] =   min(p[Mini], Mini); //字典序的邊    l[m++] = max(p[Mini], Mini); //同上   }   for(j = 1; j <= n; j++) //僞松弛，更新樹臨邊節點的key值并維護p域    if(!vis[j] && edge[Mini][j] < key[j])    {key[j] = edge[Mini][j]; p[j] = Mini;}  }  cout << m << endl;  for(i = 0; i < m; i++) cout << f[i] << ' ' << l[i] << endl;  cout << ans;  return 0; }