最優布線問題

ssl 1612

題目大意：

求最小生成樹

原題：

題目描述

學校有n臺計算機，為了方便數據傳輸，現要將它們用數據線連接起來。兩臺計算機被連接是指它們之間有數據線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。
當然，如果將任意兩臺計算機都用數據線連接，費用將是相當龐大的。為了節省費用，我們采用數據的間接傳輸手段，即一臺計算機可以間接的通過若干臺計算機（作為中轉）來實現與另一臺計算機的連接。
現在由你負責連接這些計算機，你的任務是使任意兩臺計算機都連通（不管是直接的或間接的）。

輸入

第一行為整數n（2<=n<=100），表示計算機的數目。此后的n行，每行n個整數。第x+1行y列的整數表示直接連接第x臺計算機和第y臺計算機的費用。

輸出

一個整數，表示最小的連接費用。

輸入樣例

3 0 1 2 1 0 1 2 1 0

輸出樣例

2

樣例解釋：

連接1和2，2和3，費用為2

解題思路：

用prim的方法，也就和Dijkstra差不多，只是賦的值不同，它是邊的權值，最后求個和就行了

代碼：

鄰接表：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,w,h,sum,ans,p[105],f[105],head[105]; struct rec {int l,to,next; }a[10005]; int main() {scanf("%d",&n);for (int i=1;i<=n;++i)for (int j=1;j<=n;++j){scanf("%d",&a[++w].l);if (!a[w].l){--w;continue;}a[w].to=j;//鄰接表a[w].next=head[i];head[i]=w;}memset(f,0x7f,sizeof(f));f[1]=0;for (int i=1;i<=n;++i){sum=f[0];for (int j=1;j<=n;++j)if (!p[j]&&f[j]<sum)//求最大{h=j;sum=f[j];}p[h]=1;ans+=sum;for (int j=head[h];j;j=a[j].next)//走向其他點f[a[j].to]=min(f[a[j].to],a[j].l);//路線的長度}printf("%d",ans); }

鄰接矩陣：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,w,h,x,sum,ans,p[105],f[105],a[105][105]; int main() {memset(a,0x7f,sizeof(a));//初值memset(f,0x7f,sizeof(f));scanf("%d",&n);for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)scanf("%d",&a[i][j]);f[1]=0;for (int i=1;i<=n;++i){sum=f[0];for (int j=1;j<=n;++j)if (!p[j]&&f[j]<sum)//找最大{h=j;sum=f[j];}p[h]=1;ans+=sum;for (int j=1;j<=n;++j)f[j]=min(f[j],a[h][j]);//替換}printf("%d",ans); }

總結

以上是生活随笔為你收集整理的【prim】【最小生成树】最优布线问题（ssl 1612）的全部內容，希望文章能夠幫你解決所遇到的問題。

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