[COCI2016-2017#3] Kronican

题目描述

小 Mislav 有 $N$ 个无限容量的玻璃杯，每个玻璃杯里有一些水。小 Mislav 想喝掉所有水，但不想喝超过 $K$ 杯。

小 Mislav 可以把一杯水倒到另外一个杯子里。将水从玻璃杯 $i$ 倒到玻璃杯 $j$ 所需的工作量为 $C_{i,j}$。

请你帮助他，找到最小的总工作量。

输入格式

第一行，两个正整数 $N,K$。

接下来 $N$ 行，每行 $N$ 个整数，第 $i$ 行第 $j$ 列的数为 $C_{i,j}$。

输出格式

输出一个正整数，为最小的总工作量。

样例 #1

样例输入 #1

10 1
0 7 49 23 8 30 22 44 28 23
9 0 40 15 42 42 37 3 27 29
40 12 0 3 19 9 7 10 33 49
28 16 35 0 47 26 12 17 10 33
29 49 29 21 0 17 22 43 36 35
45 28 41 44 7 0 1 3 8 44
18 40 24 46 30 3 0 22 16 49
24 1 3 27 8 28 33 0 48 31
35 13 15 14 13 36 25 19 0 15
44 29 1 17 45 5 4 1 48 0

样例输出 #1

46

#include <bits/stdc++.h>
#define re register int 
using namespace std;
const int N = 30, inf = 0x3f3f3f3f;
struct edge
{
	int x, y, w;
}e[N * N];
int top, fa[N];
int n, k, ans = inf;
bool cmp(edge i, edge j) { return i.w < j.w; }

int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}

void merge(int x, int y)
{
	fa[find(x)] = find(y);
}

void kruskal()
{
	for (re i = 1; i <= n; i ++) fa[i] = i;
	sort(e + 1, e + top + 1, cmp);
	int root = 0;
	int res = 0;
	for (re add = 0; add < top; add ++) // 乱加的，反正数据不大 
	{	
		root = 0;
		res = 0;
		for (re i = 1; i <= n; i ++) fa[i] = i;
		for (re i = 1 + add; i <= top; i ++)
		{
			root = 0;
			for (re i = 1; i <= n; i ++) 
				if (fa[i] == i) root ++;
			if (root == k) 
			{
				ans = min(ans, res);
				break;
			}
			edge a = e[i];
			if (find(a.x) != find(a.y) && fa[a.x] == a.x) // fa[a.x] == a.x 当前有水 <--- tip 1 
			{
				merge(a.x, a.y);
				res += a.w;
			}
		}
	}
	
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for (re i = 1; i <= n; i ++)
		for (re j = 1, w; j <= n; j ++)
		{
			cin >> w;
			if (i == j) continue;
			e[++top] = (edge){i, j, w};
		}
	if (n == k)
	{
		cout << 0;
		return 0;
	}
	kruskal();
	cout << ans;
	
	return 0;
}