POJ 3925 Minimal Ratio Tree
题目链接
题意:给定一些点权和一个边权矩阵,求一个最小的比例的树
思路:先枚举用哪些点,然后求最小生成树即可
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
int n, m, val[N], edge[N][N];
int bitcount(int x) {
if (x == 0) return 0;
return bitcount(x>>1) + (x&1);
}
struct Edge {
int u, v, w;
Edge() {}
Edge(int u, int v, int w) {
this->u = u;
this->v = v;
t......
阅读全文