#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector <int> link, sz;
DSU (int s) {
link = sz = vector <int> (s+1);
for (int i = 0; i <= s; i++) {
link[i] = i;
sz[i] = 1;
}
}
int head(int x) {
if (link[x] == x)
return x;
return link[x] = head(link[x]);
}
bool same(int a, int b) {
return head(a) == head(b);
}
void unite(int a, int b) {
a = head(a);
b = head(b);
if (same(a, b))
return;
if (sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
link[b] = a;
}
};
int main() {
int n, k;
cin >> n >> k;
vector <vector <int>> adj(n, vector <int> (n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
cin >> adj[i][j];
}
vector <array <int, 3>> edges;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j)
continue;
edges.push_back({adj[i][j], i, j});
}
}
sort(edges.begin(), edges.end());
int ans = 0;
DSU dsu(n+1);
for (int i = 0; i < (int)edges.size() && k < n; i++) {
int c = edges[i][0], a = edges[i][1], b = edges[i][2];
if (dsu.same(a, b))
continue;
ans += c;
dsu.unite(a, b);
k++;
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
508 KB |
Output isn't correct |
| 7 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 8 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 9 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 10 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
