tsq0511 2016-09-25 07:41:22
点我顶贴
收藏
删除
#include<stdio.h>
#include<string.h>
int n,k,f[101][101],i,j,min[10001],x,y;
long long totfirst=0,totend=0;
int pd[101];
int main(){
int k;
scanf("%d%d",&n,&k);
memset(f,0x7f,sizeof(f));
memset(min,0x7f,sizeof(min));
memset(pd,1,sizeof(pd));
min[1]=0;
for(i=1;i<=n;i++){
scanf("%d%d",&x,&y);
scanf("%d",&f[x][y]);
f[y][x]=f[x][y];
totfirst+=f[x][y];
}
for(i=1;i<=n;i++){
k=0;
for(j=1;j<=n;j++)
if(pd[j]&&min[j]<min[k])
k=j;
pd[k]=0;
for(j=1;j<=n;j++){
if(pd[j]&&min[j]>f[k][j])
min[j]=f[k][j];
}
}
for(i=1;i<=n;i++)
totend+=min[i];
printf("%lld",totfirst-totend);
return 0;
}