#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll val[25][25];
vector<pair<ll, pii>> v;
ll n, k;
ll prt[25];
ll find(ll x){
if(prt[x] == x)
return x;
return prt[x] = find(prt[x]);
}
ll merge(ll x, ll y){
x = find(x);
y = find(y);
prt[x] = y;
}
ll bitcnt(ll x){
ll ret = 0;
while(x > 0){
ret += x%2;
x /= 2;
}
return ret;
}
ll f(ll bit){
ll ret = 0;
for(ll i = 0; i < n; ++i)
prt[i] = i;
ll root = -1;
for(ll i = 0; i < n; ++i){
if((bit&(1<<i)) == 0)
continue;
if(root == -1)
root = i;
else
merge(root, i);
}
for(auto u : v){
if(find(u.ss.ff) != find(u.ss.ss)){
ret += u.ff;
merge(u.ss.ff, u.ss.ss);
}
}
return ret;
}
ll sfunc(pair<ll, pii> a, pair<ll, pii> b){return a.ff < b.ff;}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> k;
for(ll i = 0; i < n; ++i)
for(ll j = 0; j < n; ++j){
cin >> val[i][j];
if(i != j)
v.pb({val[i][j], {i, j}});
}
sort(v.begin(), v.end(), sfunc);
ll ans = 1e9;
for(ll i = 0; i < (1<<n); ++i){
if(bitcnt(i) == k){
ans = min(ans, f(i));
//cout << i << " " << f(i) << "\n";
}
}
cout << ans << "\n";
}
Compilation message
kronican.cpp: In function 'll merge(ll, ll)':
kronican.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
396 KB |
Output isn't correct |
| 6 |
Incorrect |
5 ms |
380 KB |
Output isn't correct |
| 7 |
Incorrect |
19 ms |
376 KB |
Output isn't correct |
| 8 |
Incorrect |
33 ms |
376 KB |
Output isn't correct |
| 9 |
Incorrect |
25 ms |
376 KB |
Output isn't correct |
| 10 |
Incorrect |
256 ms |
504 KB |
Output isn't correct |
