最小樹（二）(最小生成樹prim)

description

在森林裡住了n隻小熊，他們分别叫小熊A，小熊B……，小熊們決定修建水泥路讓他們能更加友善的往來，使得任何一隻小熊都能輕松到達其他小熊的家，同時小熊們希望修建的水泥路最短。

input

測試輸入若幹執行個體，每個測試執行個體第一行給出小熊的數目n和小熊們能直接通往的m條道路，（n,m < 100)接下來m行，每行為兩隻小熊的名字（分别為A,B,C.........,若n為3，則隻會出現A,B,C,依次類推）以及這兩隻小熊之間的距離（為正整數）。

output

輸出最短的水泥路的長度，若不能滿足任何一隻小熊到其他所有小熊的家，則輸出-1.

sample_input

3 3 A B 1 A C 2 B C 4 3 1 A B 2

sample_output

3 -1 AC 代碼: #include<iostream> #include<cstdio> #include<string.h> using namespace std; #define MAX 99999 #define LEN 101 int dist[LEN]; int map[LEN][LEN]; bool isvisited[LEN]; int m; void init()//這個函數是用來防止一點到另一點沒路時 { int i,j; for(i=0; i<LEN; i++) { for(j=0; j<LEN; j++) { map[i][j]=MAX; } } } int prime(int n) { int i,j,min,pos,sum; sum=0; memset(isvisited,false,sizeof(isvisited)); for(i=1; i<=n; i++) { dist[i]=map[1][i]; } isvisited[1]=true; dist[1]=MAX; for(i=1; i<n; i++) { min=MAX; for(j=1; j<=n; j++) { if(!isvisited[j] && dist[j]<min) { min=dist[j]; pos=j; } } if(min==MAX)//最小的既然都達到這個程度了，就意味着這兩點之間是不連着的 { return -1; } sum+=min; isvisited[pos]=true; for(j=1; j<=n; j++) { if(!isvisited[j] && dist[j]>map[pos][j]) { dist[j]=map[pos][j]; } } } return sum; } int main() { int n,m; while(~scanf("%d%d",&m,&n)) { init(); int i,a,b,w,ans; char c,d; if(n==0) break; for(i=0; i<n; i++) { cin>>c>>d>>w; a=c-'A'+1; b=d-'A'+1; if(map[a][b]>w) { map[a][b]=map[b][a]=w; } } ans=prime(m); cout<<ans<<endl; } return 0; }