最短網絡 (最小生成樹)

最短網絡

Description

　　農民約翰被選為他們鎮的鎮長！他其中一個競選承諾就是在鎮上建立起網際網路，并連接配接到所有的農場。當然，他需要你的幫助。約翰已經給他的農場安排了一條高速的網絡線路，他想把這條線路共享給其他農場。為了用最小的消費，他想鋪設最短的光纖去連接配接所有的農場。你将得到一份各農場之間連接配接費用的清單，你必須找出能連接配接所有農場并所用光纖最短的方案。每兩個農場間的距離不會超過100000

Input

第一行： 農場的個數，N（3<=N<=100）。

第二行…結尾: 後來的行包含了一個N*N的矩陣,表示每個農場之間的距離。理論上，他們是N行，每行由N個用空格分隔的數組成，實際上，他們限制在80個字元，是以，某些行會緊接着另一些行。當然，對角線将會是0，因為不會有線路從第i個農場到它本身。

Output

隻有一個輸出，其中包含連接配接到每個農場的光纖的最小長度。

Sample Input

4

0 4 9 21

4 0 8 17

9 8 0 16

21 17 16 0

Sample Output

28

分析

這題也是一道最小生成樹的模闆

做完這題可以去看最優布線問題（最小生成樹）

最優布線問題（最小生成樹）

裡面有知識點

直接Ctr+c然後Ctr+v就行了

AC代碼

#include<iostream>
#include<cstring>
using namespace std;
int n,k,s,a[105][105],b[105],m[105];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  cin>>a[i][j];
	memset(m,0x7f,sizeof(m));//将值弄最大
	m[1]=0;  //将第一個為0
	for(int i=1;i<=n;i++)
	{
		k=0;
		for(int j=1;j<=n;j++)
		 if(!b[j]&&(m[j]<m[k]))//如果這是藍點，并且與白點相連最短，就記錄
		  k=j;
		b[k]=1;//将這個為白點
		for(int j=1;j<=n;j++)
		 if(!b[j]&&(a[k][j]<m[j]))//如果這是藍點，并且與這個白點的距離，比與它相連的白點的值還小，就更新
		  m[j]=a[k][j];   
	}  
	for(int i=1;i<=n;i++)//加每個點的最小權值
	 s+=m[i];
	cout<<s;
} 
           

還有一個kruskal算法

#include<iostream>
using namespace std;
int n,m,x,y,s,o,v[105],a[105][105];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++)
	  cin>>a[i][j];
	for(int i=1;i<=n;i++)v[i]=i;  //給它們指派初值
	for(int k=1;k<=n-1;k++)
  	 {
      	m=2147483647;//定大點，記住不能為
      	for(int i=1;i<=n;i++)//找兩個點不在同一個集合中，最小的邊
     	for(int j=1;j<=n;j++)
      	 if((v[i]!=v[j])&&(a[i][j]<m)&&(a[i][j]!=0))
	   	  {m=a[i][j];x=i;y=j;}
      	s+=m;
      	int t=v[y];//一定要這樣
      	for(int i=1;i<=n;i++)
         if(v[i]==t)v[i]=v[x];//将這兩個集合合并
	  }
  	cout<<s;
}
           

謝謝