#include<iostream> //最小生成樹prim算法
using namespace std;
const int max_ve=1005,max_ed=15005,MaxWeight=INT_MAX;
int n,m,edge[max_ve][max_ve],sum; //n,m分别記錄頂點數和邊數
struct MST //最小生成樹的邊
{
int begin,end,weight;
}mst[max_ve];
void Prim()
{
int min,v,com,i,j,k;
for(i=0;i<n-1;i++) //對mst進行初始化，頂點下标從0開始
{
mst[i].begin=0;mst[i].end=i+1;
mst[i].weight=edge[0][i+1];
}
for(i=0;i<n-1;++i) //求n-1條邊
{
min=MaxWeight;
for(j=i;j<n-1;++j)
{
if(mst[j].weight<min) //求最小權值邊
{
min=mst[j].weight;k=j;
}
}
swap(mst[k],mst[i]); //最小邊移至前端
v=mst[i].end;
sum+=mst[i].weight;
for(j=i+1;j<n-1;++j) //更新後面的邊
{
com=edge[v][mst[j].end];
if(com<mst[j].weight)
{
mst[j].weight=com;mst[j].begin=v;
}
}
}
}
int main()
{
return 0;
}
