//無向圖最小生成樹,prim算法,鄰接陣形式,復雜度O(n^2)
//返回最小生成樹的長度,傳入圖的大小n和鄰接陣mat,不相鄰點邊權inf
//可更改邊權的類型,pre[]返回樹的構造,用父結點表示,根節點(第一個)pre值為-1
//必須保證圖的連通的!
#define MAXN 200
#define inf 1000000000
typedef double elem_t;

elem_t prim(int n,elem_t mat[][MAXN],int* pre){
	elem_t min[MAXN],ret=0;
	int v[MAXN],i,j,k;
	for (i=0;i<n;i++)
		min[i]=inf,v[i]=0,pre[i]=-1;
	for (min[j=0]=0;j<n;j++){
		for (k=-1,i=0;i<n;i++)
			if (!v[i]&&(k==-1||min[i]<min[k]))
				k=i;
		for (v[k]=1,ret+=min[k],i=0;i<n;i++)
			if (!v[i]&&mat[k][i]<min[i])
				min[i]=mat[pre[i]=k][i];
	}
	return ret;
}