最小生成树非模板题 入门已过进阶未满 （AcWing 346 poj 2728 ）_最小生成树(非模板)

1.AcWing 346 走廊泼水节

题目：https://www.acwing.com/problem/content/description/348/

用kruskal算法的思想，每加入一条边的时候，假如这条边的左右端点的祖先不属于同一个集合（并查集），就说明这两个集合是分开来的

如图，s1，s2集合，假设此时的边连接的是1，4两点，长度为z

因为最后需要生成完全图，意味着点和点之间必定有边，那么我们此时考虑s1和s2集合的点

除开1，4之外，假如有任意两个点之间的距离小于z的话，此时1，4这条边就不会作为最小生成树的其中一条边之一。

为了使得最后完全图的边长最小，而此时除了1，4两点之间的距离可以为z，其他都要大于z，因此取z+1

对于两个集合，两两点之间搭建一条z+1的边，总共为 (3*3-1)*(z+1)的长度

合并后因为这些点两两已经有边，因此将他们看成一个整体，以后合并的时候就不需要考虑他们内部的情况了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4;
struct edge {
	int fro, to, val;
}e[maxn];
bool cmp(edge a, edge b) {
	return a.val < b.val;
}
int f[maxn], siz[maxn]; //f:并查集 siz：该并查集的大小（元素个数）
int n, ans;
int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
void init() {
	ans = 0;
	for (int i = 1; i <= n; i++) f[i] = i, siz[i] = 1;
}
void kruskal() {
	sort(e + 1, e + n, cmp);
	int lef = n - 1;
	for (int i = 1; i < n; i++) {
		int fa = find(e[i].fro), fb = find(e[i].to);
		if (fa == fb) continue;
		ans += (siz[fa] * siz[fb] - 1)*(e[i].val + 1);
		f[fa] = fb;
		siz[fb] += siz[fa];
		if (--lef == 0) break;
	}
	cout << ans << endl;
 
}
int main() {
	int t; 
	cin >> t;
	while (t--) {
		cin >> n;
		init();
		for (int i = 1; i < n; i++)
			scanf("%d %d %d", &e[i].fro, &e[i].to, &e[i].val);
		kruskal();
	}
	return 0;
}

 

 

poj 2728 Desert King

原题：https://vjudge.net/problem/POJ-2728#author=CMinusMinus

（我直接看翻译了，英语太烂。。）

这道题是0/1分数规划 + 最优比率生成树

0/1 分数规划可以用二分答案来做

（注意下面的cost表示花费，val表示价值，均被我省略了数组下标）

题目要求这个东西最小

也就是存在一个最小的k，使得：

转化为乘法：

合并求和符号

也就是说，存在一个最小的k，使得上面这条式子成立

二分k，构建一棵最小生成树，点和点的权值为 cost[i]-k*val[i]，假如式子大于等于0，则r=mid，否则l=mid

而这是完全图，对于每一次二分：

建边要n^2时间复杂度

假如使用kruskal，边的数量有m= n^2（完全图），kruskal时间复杂度=mlogm = 2n^2logn,

使用kruskal总的时间复杂度n^4logn  超时

此题应该使用普里姆算法（完全图，边多）

因为是完全图，所以普里姆的堆优化没用（应该是这样的），使用堆优化的prim反而超时，要使用普通的普里姆

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
//const int INF = 0x3f3f3f3f;
const double INF = 1e10;
const int maxn = 1e3 + 7;
int xx[maxn], yy[maxn], h[maxn];
double m[maxn][maxn], cost[maxn][maxn];
double vv[maxn][maxn];
int n;
void makevv(double k) {
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			vv[i][j] = cost[i][j] - k * m[i][j];
			vv[j][i] = vv[i][j];
		}
	}
}
double dis[maxn];
bool vis[maxn];
int prim() {
	double ans = 0;
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) dis[i] = INF;
	dis[1] = 0;
	vis[1] = 1;
	int now = 1;
	for (int i = 1; i < n; i++) { //i<=n
		double minn = INF;
		int k = 1;
		for (int j = 1; j <= n; j++) {
			if (!vis[j]) {
				if (dis[j] > vv[now][j]) dis[j] = vv[now][j];
				if (dis[j] < minn) minn = dis[j], k = j;
			}
		}
		vis[k] = 1;
		ans += minn;
		cout << k << "  ans=   " << ans << endl;
		now = k;
	}
	return ans > 0;
}
int main() {
	while (cin >> n, n) {
		for (int i = 1; i <= n; i++) scanf("%d %d %d", xx + i, yy + i, h + i);
		double fl = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {
				m[i][j] = sqrt((double)(xx[i] - xx[j])*(xx[i] - xx[j]) + (double)(yy[i] - yy[j])*(yy[i] - yy[j]));
				cost[i][j] = (double)abs(h[i] - h[j]);
				fl = max(fl, cost[i][j] / m[i][j]);
			}
		}
		double l = 0, r = fl, mid = 0;
		while (r - l > 1e-6) {
			mid = (l + r) / 2;
			makevv(mid);
			int flag = prim();
			if (flag == 1) l = mid;
			else r = mid;
		}
		//printf("%.3lf\n", mid); //用c++交用这个
		printf("%.3f\n", mid);//用g++交用这个
	}
	return 0;
}