首先要判断能否构成生成树,刚开始的思路是用hash遍历城市,看是否所有的城市都记录进取,被测试数据误导,如果给这组数据(1,2)(3,4)这么没办法构成单树。
#include<stdio.h>
#include<string.h>
const int INF=0x7fffffff;
const int MAXN=110;
int hash[MAXN];
int pre[MAXN];
int map[MAXN][MAXN];
int dist[MAXN];
int n,m,ans,flag;
void Prim()
{
int i,j,k;
int min;
bool p[MAXN];
for(i=2; i<=n; i++)
{
p[i]=false;
dist[i]=map[1][i];
pre[i]=1;
}
dist[1]=0;
p[1]=true;
for(i=1; i<=n-1; i++)
{
min=INF;
k=0;
for(j=1; j<=n; j++)
{
if(!p[j] && dist[j]<min)
{
min=dist[j];
k=j;
}
}
if(k==0)//判断是否有最小生成树
{
flag=1; return ;
}
p[k]=true;
ans+=dist[k];
for(j=1; j<=n; j++)
{
if(!p[j] && map[k][j]!=INF && dist[j]>map[k][j])
{
dist[j]=map[k][j];
pre[j]=k;
}
}
}
}
int main()
{
int i,a,b,c,j;
while(scanf("%d%d",&m,&n) && m)
{
// memset(hash,0,sizeof(hash));
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
if(i==j) map[i][j]=0;
else map[i][j]=INF;
}
for(i=1; i<=m; i++)
{
scanf("%d%d%d",&a,&b,&c);
if(map[a][b]>c) map[a][b]=map[b][a]=c;
// hash[a]=hash[b]=1;
}
// for(i=1; i<=n; i++)
// if(hash[i]!=1) break;
ans=flag=0;
Prim();
if(flag) printf("?\n");
else printf("%d\n",ans);
}
return 0;
}