文章
17
粉丝
166
获赞
6
访问
143.7k
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
struct Edge
{
int a, b, w;
bool operator< (const Edge &W)const{return w < W.w;}
}edge[N];
int p[N];
int n, m;
int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
while(cin >> n >> m)
{
if(n == 0) break;
for(int i = 0; i < n; i++)
{
int a, b, w;
cin >> a >> b >> w;
edge[i] = {a, b, w};
}
sort(edge, edge + n);
int cnt = 0, ans = 0;
for(int i = 1; i <= m; i++) p[i] = i;
for(int i = 0; i < n; i++)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
a = find(a), b = find(b);
if(a != b)
{
ans += w;
cnt ++;
p[a] = b;
}
}
if(cnt < m - 1) cout << "?" << endl;
else cout << ans << endl;
}
return 0;
}
登录后发布评论
暂无评论,来抢沙发