【集训DAY12】Minn ratio 【dfs】【最小生成树】

思路：

我们直接暴力把要选的点dfs出来，然后做最小生成树就行了

$code$

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n, m, a[20], fa[20];
int head[20], tot;
int p[20], an[20];
double ans = 1000000000.0;

bool v[20];

struct node {
    
	int from, to, next, w;
}b[1000];

void add(int x, int y, int w) {
    
	b[++ tot] = (node) {
     x, y, head[x], w };
	head[x] = tot;
}

bool cmp(node x, node y) {
    
	return x.w < y.w;
}

int getfa(int x) {
    
	if(x == fa[x]) return x;
	return fa[x] = getfa(fa[x]);
}

double jis() {
    
	double dian = 0;
	for(int i = 1; i <= m; i ++) dian = dian + a[p[i]] * 1.0;
	for(int i = 1; i <= n; i ++) fa[i] = i;
	double bian = 0;
	for(int i = 1; i <= tot; i ++) {
    
		int x = b[i].from, y = b[i].to;
		if(v[x] != 1 || v[y] != 1) continue;
		int xx = getfa(x), yy = getfa(y);
		if(xx == yy) continue;
		fa[yy] = xx, bian = bian + b[i].w * 1.0;
	}
	return bian / dian;
}

void dfs(int x, int y) {
    
	if(x > n && y == m) {
    
		double sum = jis();
		if(sum < ans) {
    
			for(int  i = 1; i <= m; i ++) an[i] = p[i];
			ans = sum;
		}
		return;
	}
	if(x > n) return;
	if(m - y > n - x + 1) return;
	p[y + 1] = x, v[x] = 1;
	dfs(x + 1, y + 1);
	v[x] = 0;
	dfs(x + 1, y);
}

int main() {
    
	freopen("ratio.in", "r", stdin);
	freopen("ratio.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= n; j ++) {
    
			int x;
			scanf("%d", &x);
			if(i != j) add(i, j, x);
		}
	sort(b + 1, b + 1 + tot, cmp);
	dfs(1, 0);
	for(int i = 1; i <= m; i ++) printf("%d ", an[i]);
	return 0;
}