#include <stdio.h>
typedef struct
{
int shi;
int mo;
int weight;
}bian;
int main()
{
int i;
int N,M;
scanf("%d %d",&N,&M);
bian e[M+1];
for(i=1;i<=M;i++)
{
scanf("%d %d %d",&e[i].shi,&e[i].mo,&e[i].weight);
}
int p=0,q=0,h=0,min=1000,zmin=0;
int j,dian1,dian2,sn1,sn2,k=0;
int vest[1000];
vest[0]=0;
for(i=1;i<=N;i++){
vest[i]=i;
}
for(h;h<=M;h++)
{
for(p=1;p<=M;p++)
{
if(e[p].weight<=min&&e[p].weight!=0)
{
min=e[p].weight;
q=p;
}
}
e[q].weight=0;
dian1=e[q].shi; dian2=e[q].mo;
sn1=vest[dian1]; sn2=vest[dian2];
if(sn1!=sn2)
{
k++;
zmin=zmin+min;
if(k==N-1) break;
for(i=1;i<=N;i++)
{
if(vest[i]==sn1)
vest[i]=sn2;
}
}
}
if(k!=N-1)
printf("Impossible");
else printf("%d",zmin);
return 0;
｝
最小N是2 当只有两个工程一条边时我的算法能得到结果
