- it
- HDOJ 1863（并查集+Kruskal）
#include <stdio.h>
#include <algorithm>
#include <list>
#include <vector>
#include <iostream>
using namespace std
;
#define MAX 1000
typedef struct path
{
int s
,e
,v
;
}path
;
int n
,m
,be
[MAX
];
bool vis
[MAX
];
vector
<int> map
[MAX
];
vector
<path
> p
;
void init(){
for(int i
= 0;i
< MAX
;i
++){
vis
[i
] = false;
be
[i
] = i
;
map
[i
].clear();
}
p
.clear();
}
bool cmp(path
&a
,path
&b
){
return a
.v
< b
.v
;
}
int find(int c
){
return (be
[c
] == c
)?(c
):(be
[c
] = find(be
[c
]));
}
int Kruskal(){
int count
,ans
;
ans
= count
= 0;
for(int i
= 0;i
< p
.size();i
++){
if(find(p
[i
].s
) != find(p
[i
].e
)){
ans
+= p
[i
].v
;
count
++;
be
[be
[p
[i
].s
]] = be
[p
[i
].e
];
}
}
if(count
== m
-1){
return ans
;
}
return -1;
}
int main(){
scanf("%d%d",&n
,&m
);
while(n
!=0){
init();
for(int i
= 0;i
< n
;i
++){
path tmp
;
scanf("%d%d%d",&tmp
.s
,&tmp
.e
,&tmp
.v
);
p
.push_back(tmp
);
}
sort(p
.begin(),p
.end(),cmp
);
int ans
= Kruskal();
if(ans
== -1){
printf("?\n");
}else{
printf("%d\n",ans
);
}
scanf("%d%d",&n
,&m
);
}
return 0;
}
