最小生成樹。Prim或者Kruskal。
以下Prim算法，輸入矩陣：
#include<stdio.h>
int d[103][103],flag[103],lowcost[103],link[103],a[103],b[103];
int main()
{
int n,i,j,min,minj,tot;
while (scanf("%d",&n)==1)
{
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&d[i][j]);
for (i=1;i<=n;i++)
{
flag[i]=1;
lowcost[i]=1000000;
link[i]=1;
}
for (i=1;i<=n;i++)
if (d[1][i])
lowcost[i]=d[1][i];
flag[1]=0;tot=0;
for (i=2;i<=n;i++)
{
min=1000000;
for (j=2;j<=n;j++)
if (flag[j]&&min>lowcost[j])
{
min=lowcost[j];
minj=j;
}
flag[minj]=0;tot+=min;
for (j=2;j<=n;j++)
if (flag[j]&&d[minj][j]&&lowcost[j]>d[minj][j])
{
lowcost[j]=d[minj][j];
link[j]=minj;
}
}
printf("%d\n",tot);
}
}
哦哦，a[],b[]用來記錄生成樹的邊的。這里沒有用上。啊，n^2,這個復(fù)雜度不行啊，得學(xué)學(xué)高級的方法才行啊。