제출 #1174778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1174778		nuutsnoynton	Kronican (COCI16_kronican)	C++20	10 / 100	64 ms	328 KiB

kronican

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
ll D[22][22] = {0}, d[22], ataman[22];
ll Get(ll x) {
	if (x == ataman[x]) return x;
	return ataman[x] = Get(ataman[x]);
}
int main() {
	ll n, m, r, x, s,node, y, k, i,sum, j, ans, t;

	cin >> n >> k;
	vector < pair < ll , pair < ll, ll > > > q;
	for (i = 1; i <= n; i ++) {
		for (j = 1; j <= n; j ++) {
			cin >> D[i][j];
			q.push_back(make_pair(D[i][j], make_pair(i, j)));
		}
	}
	
	sort(q.begin(), q.end());
	
	vector <ll > v;
	
	for (i = 1; i <= k; i ++) {
		v.push_back(i);		
	}
	ans = 1e17;
	while(1) {
		for (i = 1; i <= n; i ++) ataman[i] = i;
		sum = 0;
		for (i = 0; i < v.size(); i ++) {
			ataman[v[i]] = v[0]; 
		}
		for (i = 0; i < q.size(); i ++) {
			x = q[i].second.first;
			y = q[i].second.second;
			if ( Get(x) != Get(y)) {
				ataman[Get(x)] = Get(y);
				sum += q[i].first;
			}
		}
		ans = min(ans, sum);
		r = v.size();
		ll p = n;
		//cout << r << endl;
		while (r > 0 && v[r - 1] == p) {
			r --;
			p --;
		}
		if ( r == 0) break;
		v[r - 1] ++;
		while ( r <v.size()) {
			v[r] = v[r - 1] + 1;
			r ++;
		}
		
	}
	cout << ans << endl;
}

• Subtask 1: 10 / 100