http://poj.org/problem?id=1258
今天晚上随便找了两道题，没想到两道都是我第一次碰到的类型———最小生成树。我以前并没有见过，也不知道怎么做，然后就看书，思路很容易理解
但我最开始确想错了，我想成每一个点只可以连接一个或者两个地方，所以那样写出来的答案根本就是错误的，也不是这个树所表达的意思
最后多次对书上的算法接合案例一步一步的进行推倒，才发现我的想法是错了，用了一个多小时
#include <stdio.h>
#include <string.h> #define inf 100009 bool mark[];
int a[][],dis[],ans,n; int prim()
{
for(int i=;i<=n;i++)
dis[i]=inf;dis[]=;
for(int i=;i<=n;i++){ //其内涵就是用dis数组来记录下每一列的最小的长度，然后加起来也便是最小的长度
int tep=inf;int k=;
for(int j=;j<=n;j++){
if(mark[j]&&dis[j]<tep) //有n个相连的话，最短需要连接n-1次，也可以看出是连接n次，那就是还有一个是自己连接自己，长度为0。
{
tep=dis[j];
k=j;
}
}
if(tep==inf) return ;
ans+=tep;
mark[k]=false;
for(int j=;j<=n;j++)
if(mark[j]&&dis[j]>a[k][j])
dis[j]=a[k][j];
}
return ;
} int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(mark,true,sizeof(mark));
ans=;
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&a[i][j]);
prim();
printf("%d\n",ans);
}
}