include iostream include vector include algorithm using namespace std

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> p;
int find (int a)
{
if (a == p[a])
return a;
else
return p[a] = find(p[a]);
}
bool dsu(int a, int b)
{
int A = find(a), B = find(b);
if (A != B)
{
if (rand() % 2)
swap(a,b);
p[A] = B;
return true;
}
else
return false;
}
int main()
{
int n, m;
cin >> n >> m;
p.resize(n);
vector<pair<int, pair<int, int> > > planet(m), best_ans(n - 1), ans1(n - 1), ans2(n - 1);
for (int i = 0; i < n; ++i)
p[i] = i;
for (int i = 0; i < m; ++i)
{
cin >> planet[i].second.first >> planet[i].second.second >> planet[i].first;
planet[i].second.first--;
planet[i].second.second--;
}
sort(planet.begin(), planet.end());
int k = 0, best_s = 0, s1 = 600 * 1000, s2 = 0;
for (int i = 0; i < m; ++i)
{
if ( dsu(planet[i].second.first, planet[i].second.second) )
{
best_ans[k] = planet[i];
best_s += best_ans[k].first;
k++;
}
}
for (int j = 0; j < n - 1; ++j)
{
k = 0;
s2 = 0;
for (int i = 0; i < n; ++i)
p[i] = i;
for (int i = 0; i < m; ++i)
{
if (planet[i] == best_ans[j])
continue;
else
{
if ( dsu(planet[i].second.first, planet[i].second.second) )
{
ans2[k] = planet[i];
s2 += ans2[k].first;
k++;
}
}
}
if(s2 < s1 && k == (n - 1) )
{
for (int q = 0; q < n - 1; ++q)
ans1[q] = ans2[q];
s1 = s2;
}
}
cout << "Cost: " << best_s << endl;
if (s1 == 600 * 1000)
cout << "Cost: " << -1 << endl;
else
cout << "Cost: " << s1 << endl;
return 0;
}