最小生成树

两个最小生成树(Minimum Spanning Tree, MST)算法完全等价。

如果输入邻接矩阵，一般用Prim。

如果输入边表，一般用Kruskal。

性质

环性质(Cycle property)
对于一个环C，如果其中一条边e的边权严格大于C中其他所有的边，那么这条边不可能属于最小生成树。
For any cycle C in the graph, if the weight of an edge e of C is larger than the individual weights of all other edges of C, then this edge cannot belong to an MST.

割性质(Cut property)
对于一个割C，如果其中一条边e的边权严格小于C中其他所有的边，那么这条边一定属于最小生成树。
For any cut C of the graph, if the weight of an edge e in the cut-set of C is strictly smaller than the weights of all other edges of the cut-set of C, then this edge belongs to all MSTs of the graph.

Borůvka's algorithm

对于每个点，权值最小的边一定会被选择

参考题目

参考资料

https://en.wikipedia.org/wiki/Minimum_spanning_tree
https://en.wikipedia.org/wiki/Prim's_algorithm
https://en.wikipedia.org/wiki/Kruskal's_algorithm

Prim

Prim's algorithm

可以使用堆优化，类似Dijkstra，但是使用堆优化，效率未必提高。

对于完全图的情况：

不使用堆优化，时间复杂度为$O(n^2)$；

使用堆优化，时间复杂度为$O(n^2 \log n)$。

所以说对于以邻接矩阵输入的图，没必要去用Kruskal。

参考代码（Luogu P1265）：

#include <bits/stdc++.h>
using namespace std;
int n;
double x[5020], y[5020];
double d[5020];
bool v[5020];
double ans;
double dist(int i, int j) {
    // 返回点i和点j之间的距离。
    return hypot(x[i] - x[j], y[i] - y[j]);
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 1; i < n; i++) {
        d[i] = 1e30;
    }
    // 除了0号点，每个点距离都初始化为无穷大。
    for (int i = 0; i < n; i++) {
        int mini = -1;
        double mind = 1e30;
        for (int j = 0; j < n; j++) {
            if (!v[j]) {
                if (mind > d[j]) {
                    mind = d[j];
                    mini = j;
                }
            }
        }
        // 每次找到未被标记的点中，距离最近的点。
        ans += mind;
        v[mini] = true;
        // 选择连向这个点的边，并标记这个点已被选择。
        for (int j = 0; j < n; j++) {
            if (!v[j]) {
                d[j] = min(d[j], dist(j, mini));
                // 更新剩余所有点的距离。
            }
        }
    }
    cout << fixed << setprecision(2) << ans << endl;
    return 0;
}

$O(n^2)$

n is the number of vertices.

The edge with minimum weight in a cut must be in MST.

2 arrays
visited, whether we have chosen this vertex.
distance, the minimum distance from this vertex to a chosen vertex.

do n times
find the vertex min_i with minimum distance, it is not chosen. n * O(n) -> n * O(log n)
ans += d[min_i]
v[min_i]
for each edge starting from min_i to j, the length dist(min_i, j) O(m) -> O(m log m)
d[j] = min(d[j], dist(min_i, j))

If the graph is a complete graph, we will use prim's algorithm.

Prim：只对完全图使用
时间复杂度O(n^2)
但是不能输入n^2个数字，只能输入n个，所以距离是通过某种方式算出来的

需要2个数组
v数组，标记数组，表示每个点是否已经被选择
d数组，距离数组，表示每个点到已经选择的集合的距离的最小值是多少

v数组初始化0，表示都没有被选择
d数组初始化无穷大，因为没已经选择的集合
d中初的起点始化为0，保证第一个选择的是起点

做n轮 // 每个点恰好被选1次
找到d数组中，未被标记的位置中的最小值d[min_i]，还需要记录最小值的位置min_i
ans += 最小值d[min_i]
标记最小值的位置min_i为选择 v[min_i] = true
枚举从min_i出发的所有的边(min_i, j, dist(min_i, j))，
如果j没有被标记过
更新d[j] = min(d[j], dist(min_i, j))
// 根据需要，考虑是否需要记录是谁更新的j

ans = 0 + 最小生成树上(n-1)个边权
d数组中存的是0和最小生成树上(n-1)个边权

Luogu P1265
Prim最小生成树（完全图，邻接矩阵）

Luogu P2872
Prim最小生成树（完全图，邻接矩阵）但是需要考虑权值为0的边

Luogu P2212
Prim最小生成树（完全图，邻接矩阵）如果边权小于c，那么返回$+\infty$

Luogu P1546
最小生成树（邻接矩阵） 推荐Prim，也可以Kruskal

Kruskal's algorithm

先对所有边排序，从小到大依次选择，能选则选，选不了就放弃，用并查集判断能否选择。

可以求最小生成森林，也就是算法只执行到合适的连通块数就推出。

时间复杂度和把所有边排序的复杂度一样，为$O(m \log m)$。

如果只需要求最小生成树的最大边的权值，可以在$O(m)$的时间内求出。
（二分，每次丢掉一半）

参考题目

P1546 [USACO3.1]最短网络 Agri-Net

https://www.luogu.com.cn/problem/P1546

题目背景

Farmer John 被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。

题目描述

FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 $10^5$。

输入格式

第一行农场的个数 $N$（$3 \leq N \leq 100$）。

接下来是一个 $N \times N$ 的矩阵，表示每个农场之间的距离。理论上，他们是 $N$ 行，每行由 $N$ 个用空格分隔的数组成，实际上，由于每行 $80$ 个字符的限制，因此，某些行会紧接着另一些行。当然，对角线将会是 $0$，因为不会有线路从第 $i$ 个农场到它本身。

输出格式

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

样例 #1

样例输入 #1

4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0

样例输出 #1

28

提示

题目翻译来自NOCOW。

USACO Training Section 3.1

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int a[120][120];
int d[120];
bool v[120];
int ans;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i < n; i++) {
		d[i] = 1e9;
	}
	for (int i = 0; i < n; i++) {
		int mini = -1;
		int mind = 1e9;
		for (int j = 0; j < n; j++) {
			if (!v[j]) {
				if (mind > d[j]) {
					mind = d[j];
					mini = j;
				}
			}
		}
		ans += mind;
		v[mini] = true;
		for (int j = 0; j < n; j++) {
			if (!v[j]) {
				d[j] = min(d[j], a[j][mini]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}

题解

P1547 [USACO05MAR]Out of Hay S

https://www.luogu.com.cn/problem/P1547

题目描述

Bessie 计划调查 $N$（$2 \leq N \leq 2\,000$）个农场的干草情况，它从 $1$ 号农场出发。农场之间总共有 $M$（$1 \leq M \leq 10^4$）条双向道路，所有道路的总长度不超过 $10^9$。有些农场之间存在着多条道路，所有的农场之间都是连通的。

Bessie 希望计算出该图中最小生成树中的最长边的长度。

输入格式

第一行两个整数 $N,M$。

接下来 $M$ 行，每行三个用空格隔开的整数 $A_i,B_i,L_i$，表示 $A_i,B_i$ 之间有一条道路，长度为 $L_i$。

输出格式

一个整数，表示最小生成树中的最长边的长度。

样例 #1

样例输入 #1

3 3
1 2 23
2 3 1000
1 3 43

样例输出 #1

43

提示

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[2020];
int n, m;
long long ans;
pair<int, pair<int, int> > a[10020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
	}
	sort(a, a + m);
	for (int i = 0; i < m; i++) {
		int x = F(a[i].second.first);
		int y = F(a[i].second.second);
		if (x != y) {
			f[x] = y;
			ans = a[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

题解

P5425 [USACO19OPEN]I Would Walk 500 Miles G

https://www.luogu.com.cn/problem/P5425

题目描述

Farmer John想要将他的编号为 $1 \ldots N$ 的 $N$ 头奶牛（ $N \leq 7500$ ）分为非空的 $K$ 组（ $2 \leq K \leq N$ ），使得任意两头来自不同组的奶牛都需要走一定的距离才能相遇。奶牛 $x$ 和奶牛 $y$ （其中 $1 \leq x<y \leq N$ ）愿意为了见面走 $(2019201913x+2019201949y) \mod 2019201997$ 英里。

给定一个将 $N$ 头奶牛分为 $K$ 个非空小组的分组方案，令 $M$ 为任意两头来自不同组的奶牛愿意为了见面行走的英里数的最小值。为了测试奶牛们相互之间的忠诚度，Farmer John想要将 $N$ 头奶牛以最佳的方式分为 $K$ 组，使得 $M$ 尽可能大。

输入格式

输入仅有一行，包含 $N$ 和 $K$ ，用空格分隔。

输出格式

输出最优的 $M$ 。

样例 #1

样例输入 #1

3 2

样例输出 #1

2019201769

提示

在这个例子中，奶牛1和奶牛2愿意为了见面走2019201817英里。奶牛2和奶牛3愿意走2019201685英里。奶牛1和奶牛3愿意走2019201769英里。所以，将奶牛1单独分为一组，奶牛2和奶牛3分为一组， $M=min(2019201817,2019201769)=2019201769$ （这是我们在这个问题中能够达到的最佳结果）。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
long long d[10000];
bool v[10000];
long long get(long long x, long long y) {
	if (x > y) {
		swap(x, y);
	}
	return ((2019201913 * x + 2019201949 * y) % 2019201997);
}

int main() {
	cin >> n >> m;
	cout << (2019202081 - 48 * n - 84 * m) << endl;
	return 0;
	memset(d, 0x3f, sizeof d);
	d[1] = 0;
	for (int i = 1; i <= n; i++) {
		int mini = -1;
		long long mind = 1e18;
		for (int j = 1; j <= n; j++) {
			if (!v[j]) {
				if (mind > d[j]) {
					mind = d[j];
					mini = j;
				}
			}
		}
		v[mini] = true;
		for (int j = 1; j <= n; j++) {
			if (!v[j]) {
				d[j] = min(d[j], get(j, mini));
			}
		}
	}
	sort(d + 1, d + 1 + n);
	cout << d[n - m + 2] << endl;
	return 0;
}

题解

P2906 [USACO08OPEN]Cow Neighborhoods G

https://www.luogu.com.cn/problem/P2906

题目描述

Those Who Know About Cows are aware of the way cows group into 'Cow Neighborhoods'. They have observed Farmer John's N (1 <= N <= 100,000) cows (conveniently numbered 1..N) as they graze, each at her own unique integer rectilinear coordinate, on a pasture whose X and Y coordinates are in the range 1..1,000,000,000.

Two cows are neighbors if at least one of two criteria is met:

1. If the cows are no further than some integer Manhattan distance C (1 <= C <= 1,000,000,000) apart, they are neighbors. [Manhattan distance is calculated as d = |x1-x2| + |y1-y2|.]
2. If cow A is a neighbor of cow Z and cow B is a neighbor of cow Z, then cow A is a neighbor of cow B (the 'transitive closure of neighbors').

Given the locations of the cows and the distance C, determine the the number of neighborhoods and the number of cows in the largest neighborhood.

By way of example, consider the pasture below. When C = 4, this pasture has four neighborhoods: a big one on the left, two neighborhoods of size 1 (the lonesome cows), and a huge neighborhood on the right with 60 different cows.

.....................................*................. 
....*...*..*.......................***................. 
......*...........................****................. 
..*....*..*.......................*...*.******.*.*..... 
........................*.............***...***...*.... 
*..*..*...*..........................*..*...*..*...*... 
.....................................*..*...*..*....... 
.....................................*..*...*..*....... 
...*................*.................................. 
.*..*............................*.*.*.*.*.*.*.*.*.*.*. 
.*.....*..........................*.*.*.*.*.*.*.*.*.*.* 
....*.................................................. 

The input file describes cow locations by integer X,Y coordinates, where the lower left corner is (1,1) and cows close to that corner appear at both (2,2) and (5,1) in the example above.

For a given pasture, determine both the number of cow neighborhoods and the number of cows resident in the largest cow neighborhood.

The above picture is sample test case 2, which will be evaluated for you upon submission.

Partial feedback for some test cases will be provided on the first 10 submissions.

Time Limit: 2 seconds

Memory Limit: 32MB

了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标$X_i,Y_i(1\leq X_i,Y_i\leq [1 \cdots 10^9]$；$X_i,Y_i \in \text{整数}$．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的：

1．两只奶牛的曼哈顿距离不超过$C(1\leq C\leq 10^9)$，即$|X_i - x_i|+|Y_i - y_i|\leq C$.

2．两只奶牛有共同的邻居．即，存在一只奶牛$k$，使$i$与$k$，$j$与$k$均同属一个群．

给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有多少奶牛

输入格式

* Line 1: Two space-separated integers: N and C

* Lines 2..N+1: Line i+1 describes cow i's location with two

space-separated integers: X_i and Y_i

输出格式

* Line 1: A single line with a two space-separated integers: the number of cow neighborhoods and the size of the largest cow neighborhood.

样例 #1

样例输入 #1

4 2 
1 1 
3 3 
2 2 
10 10 

样例输出 #1

2 3 

提示

There are 2 neighborhoods, one formed by the first three cows and the other being the last cow. The largest neighborhood therefore has size 3.

参考代码

#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[100020];
int c[100020];
int f[100020];
int n, l, x, y;
int F(int x)
{
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main()
{
	scanf("%d%d", &n, &l);
	for (int i = 0; i < n; i++)
	{
		scanf("%d%d", &x, &y);
		a[i].first = x + y;
		a[i].second = x - y;
		f[i] = i;
	}
	sort(a, a + n);
	set<pair<int, int> > s;
	for (int i = 0, j = 0; i < n; i++)
	{
		while (a[i].first - a[j].first > l)
		{
			s.erase(make_pair(a[j].second, j));
			j++;
		}
		set<pair<int, int> >::iterator it = s.lower_bound(make_pair(a[i].second, 0));
		if (it != s.end() && it->first - a[i].second <= l)
		{
			f[F(i)] = F(it->second);
		}
		if (it != s.begin())
		{
			it--;
			if (a[i].second - it->first <= l)
			{
				f[F(i)] = F(it->second);
			}
		}
		s.insert(make_pair(a[i].second, i));
	}
	int ans1 = 0, ans2 = 0;
	for (int i = 0; i < n; i++)
	{
		if (F(i) == i)
		{
			ans1++;
		}
		ans2 = max(ans2, ++c[F(i)]);
	}
	printf("%d %d\n", ans1, ans2);
	return 0;
}

题解

P2916 [USACO08NOV]Cheering up the Cow G

https://www.luogu.com.cn/problem/P2916

题目描述

Farmer John has grown so lazy that he no longer wants to continue maintaining the cow paths that currently provide a way to visit each of his N (5 <= N <= 10,000) pastures (conveniently numbered 1..N). Each and every pasture is home to one cow. FJ plans to remove as many of the P (N-1 <= P <= 100,000) paths as possible while keeping the pastures connected. You must determine which N-1 paths to keep.

Bidirectional path j connects pastures S_j and E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j) and requires L_j (0 <= L_j <= 1,000) time to traverse. No pair of pastures is directly connected by more than one path.

The cows are sad that their transportation system is being reduced. You must visit each cow at least once every day to cheer her up. Every time you visit pasture i (even if you're just traveling

through), you must talk to the cow for time C_i (1 <= C_i <= 1,000).

You will spend each night in the same pasture (which you will choose) until the cows have recovered from their sadness. You will end up talking to the cow in the sleeping pasture at least in the morning when you wake up and in the evening after you have returned to sleep.

Assuming that Farmer John follows your suggestions of which paths to keep and you pick the optimal pasture to sleep in, determine the minimal amount of time it will take you to visit each cow at least once in a day.

For your first 10 submissions, you will be provided with the results of running your program on a part of the actual test data.

POINTS: 300

约翰有N个牧场，编号依次为1到N。每个牧场里住着一头奶牛。连接这些牧场的有P条道路，每条道路都是双向的。第j条道路连接的是牧场Sj和Ej，通行需要Lj的时间。两牧场之间最多只有一条道路。约翰打算在保持各牧场连通的情况下去掉尽量多的道路。

约翰知道，在道路被强拆后，奶牛会非常伤心，所以他计划拆除道路之后就去忽悠她们。约翰可以选择从任意一个牧场出发开始他维稳工作。当他走访完所有的奶牛之后，还要回到他的出发地。每次路过牧场i的时候，他必须花Ci的时间和奶牛交谈，即使之前已经做过工作了，也要留下来再谈一次。注意约翰在出发和回去的时候，都要和出发地的奶牛谈一次话。请你计算一下，约翰要拆除哪些道路，才能让忽悠奶牛的时间变得最少？

输入格式

* Line 1: Two space-separated integers: N and P

* Lines 2..N+1: Line i+1 contains a single integer: C_i

* Lines N+2..N+P+1: Line N+j+1 contains three space-separated

integers: S_j, E_j, and L_j

输出格式

* Line 1: A single integer, the total time it takes to visit all the cows (including the two visits to the cow in your

sleeping-pasture)

样例 #1

样例输入 #1

5 7 
10 
10 
20 
6 
30 
1 2 5 
2 3 5 
2 4 12 
3 4 17 
2 5 15 
3 5 6 
4 5 12 

样例输出 #1

176 

提示

   +-(15)-+ 
  /        \ 
 /          \ 
1-(5)-2-(5)-3-(6)--5 
   \   /(17)  / 
(12)\ /      /(12) 
     4------+ 

Keep these paths: 
1-(5)-2-(5)-3      5 
       \          / 
    (12)\        /(12) 
        *4------+ 

Wake up in pasture 4 and visit pastures in the order 4, 5, 4, 2, 3, 2, 1, 2, 4 yielding a total time of 176 before going back to sleep.

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[10020];
int w[10020];
int n, m;
int ans;
pair<int, pair<int, int> > a[100020];
int F(int x) {
	if (f[x] == x) {
		return x;
	}
	f[x] = F(f[x]);
	return f[x];
}
int main() {
	cin >> n >> m;
	ans = 1e9;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
		cin >> w[i];
		ans = min(ans, w[i]);
	}
	for (int i = 0; i < m; i++) {
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
		a[i].first *= 2;
		a[i].first += w[a[i].second.first];
		a[i].first += w[a[i].second.second];
	}
	sort(a, a + m);
	for (int i = 0; i < m; i++) {
		int x = F(a[i].second.first);
		int y = F(a[i].second.second);
		if (x != y) {
			f[x] = y;
			ans += a[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

题解

P2212 [USACO14MAR]Watering the Fields S

https://www.luogu.com.cn/problem/P2212

题目描述

Due to a lack of rain, Farmer John wants to build an irrigation system to

send water between his N fields (1 <= N <= 2000).

Each field i is described by a distinct point (xi, yi) in the 2D plane,

with 0 <= xi, yi <= 1000. The cost of building a water pipe between two

fields i and j is equal to the squared Euclidean distance between them:

(xi - xj)^2 + (yi - yj)^2

FJ would like to build a minimum-cost system of pipes so that all of his

fields are linked together -- so that water in any field can follow a

sequence of pipes to reach any other field.

Unfortunately, the contractor who is helping FJ install his irrigation

system refuses to install any pipe unless its cost (squared Euclidean

length) is at least C (1 <= C <= 1,000,000).

Please help FJ compute the minimum amount he will need pay to connect all

his fields with a network of pipes.

给定 $n$ 个点，第 $i$ 个点的坐标为 $(x_i,y_i)$，如果想连通第 $i$ 个点与第 $j$ 个点，需要耗费的代价为两点的距离。第 $i$ 个点与第 $j$ 个点之间的距离使用欧几里得距离的平方进行计算，即：
$$(x_i-x_j)^2+(y_i-y_j)^2$$
我们规定耗费代价小于 $c$ 的两点无法连通，求使得每两点都能连通下的最小代价，如果无法连通输出 -1。

输入格式

* Line 1: The integers N and C.

* Lines 2..1+N: Line i+1 contains the integers xi and yi.

第一行两个整数 $n,c$ 代表点数与想要连通代价不能少于的一个数。
接下来 $n$ 行每行两个整数 $x_i,y_i$ 描述第 $i$ 个点。

输出格式

* Line 1: The minimum cost of a network of pipes connecting the

fields, or -1 if no such network can be built.

一行一个整数代表使得每两点都能连通下的最小代价，如果无法连通输出 -1。

样例 #1

样例输入 #1

3 11
0 2
5 0
4 3

样例输出 #1

46

提示

INPUT DETAILS:

There are 3 fields, at locations (0,2), (5,0), and (4,3). The contractor

will only install pipes of cost at least 11.

OUTPUT DETAILS:

FJ cannot build a pipe between the fields at (4,3) and (5,0), since its

cost would be only 10. He therefore builds a pipe between (0,2) and (5,0)

at cost 29, and a pipe between (0,2) and (4,3) at cost 17.

Source: USACO 2014 March Contest, Silver

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 2000$，$0 \le x_i,y_i \le 1000$，$1 \le c \le 10^6$。

说明

Translated by 一只书虫仔。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, c;
int x[2020], y[2020];
int d[2020];
bool v[2020];
int ans;
int dist(int i, int j) {
	int d = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
	if (d < c) {
		return 1e9;
	} else {
		return d;
	}
}
int main() {
	cin >> n >> c;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	for (int i = 1; i < n; i++) {
		d[i] = 1e9;
	}
	for (int i = 0; i < n; i++) {
		int mini = -1;
		int mind = 1e9;
		for (int j = 0; j < n; j++) {
			if (!v[j]) {
				if (mind > d[j]) {
					mind = d[j];
					mini = j;
				}
			}
		}
		if (mini == -1) {
			cout << -1 << endl;
			return 0;
		}
		ans += mind;
		v[mini] = true;
		for (int j = 0; j < n; j++) {
			if (!v[j]) {
				d[j] = min(d[j], dist(j, mini));
			}
		}
	}
	cout << ans << endl;
	return 0;
}

题解

P2872 [USACO07DEC]Building Roads S

https://www.luogu.com.cn/problem/P2872

题目描述

Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.

Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.

给定 $n$ 个点的坐标，第 $i$ 个点的坐标为 $(x_i,y_i)$，这 $n$ 个点编号为 $1$ 到 $n$。给定 $m$ 条边，第 $i$ 条边连接第 $u_i$ 个点和第 $v_i$ 个点。现在要求你添加一些边，并且能使得任意一点都可以连通其他所有点。求添加的边的总长度的最小值。

输入格式

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Two space-separated integers: Xi and Yi

* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.

第一行两个整数 $n,m$ 代表点数与边数。
接下来 $n$ 行每行两个整数 $x_i,y_i$ 代表第 $i$ 个点的坐标。
接下来 $m$ 行每行两个整数 $u_i,v_i$ 代表第 $i$ 条边连接第 $u_i$ 个点和第 $v_i$ 个点。

输出格式

* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.

一行一个实数代表添加的边的最小长度，要求保留两位小数，为了避免误差， 请用 $64$ 位实型变量进行计算。

样例 #1

样例输入 #1

4 1
1 1
3 1
2 3
4 3
1 4

样例输出 #1

4.00

提示

数据规模与约定

对于 $100\%$ 的整数，$1 \le n,m \le 1000$，$1 \le x_i,y_i \le 10^6$，$1 \le u_i,v_i \le n$。

说明

Translated by 一只书虫仔。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
double x[1020], y[1020];
double a[1020][1020];
double d[1020];
bool v[1020];
double ans;
double dist(int i, int j) {
	return hypot(x[i] - x[j], y[i] - y[j]);
}
int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			a[i][j] = dist(i, j);
		}
	}
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		x--;
		y--;
		a[x][y] = a[y][x] = 0;
	}
	for (int i = 1; i < n; i++) {
		d[i] = 1e30;
	}
	for (int i = 0; i < n; i++) {
		int mini = -1;
		double mind = 1e30;
		for (int j = 0; j < n; j++) {
			if (!v[j]) {
				if (mind > d[j]) {
					mind = d[j];
					mini = j;
				}
			}
		}
		ans += mind;
		v[mini] = true;
		for (int j = 0; j < n; j++) {
			if (!v[j]) {
				d[j] = min(d[j], a[j][mini]);
			}
		}
	}
	cout << fixed << setprecision(2) << ans << endl;
	return 0;
}

题解

P4643 [国家集训队]阿狸和桃子的游戏

https://www.luogu.com.cn/problem/P4643

题目描述

阿狸和桃子正在玩一个游戏，游戏是在一个带权图G=(V, E)上进行的，设节点权值为w(v)，边权为c(e)。游戏规则是这样的：

1. 阿狸和桃子轮流将图中的顶点染色，阿狸会将顶点染成红色，桃子会将顶点染成粉色。已经被染过色的点不能再染了，而且每一轮都必须给一个且仅一个顶点染色。

2. 为了保证公平性，节点的个数N为偶数。

3. 经过N/2轮游戏之后，两人都得到了一个顶点集合。对于顶点集合S，得分计算方式为

$$\sum_{v \in S}w(v) + \sum_{e=(u,v)\in E \land u,v\in S}c(e)$$

由于阿狸石头剪子布输给了桃子，所以桃子先染色。两人都想要使自己的分数比对方多，且多得越多越好。如果两人都是采用最优策略的，求最终桃子的分数减去阿狸的分数。

输入格式

输入第一行包含两个正整数N和M，分别表示图G的节点数和边数，保证N一定是偶数。

接下来N+M行。

前N行，每行一个整数w，其中第k行为节点k的权值。

后M行，每行三个用空格隔开的整数a b c，表示一条连接节点a和节点b的边，权值为c。

输出格式

输出仅包含一个整数，为桃子的得分减去阿狸的得分。

样例 #1

样例输入 #1

4 4
6
4
-1
-2
1 2 1
2 3 6
3 4 3
1 4 5

样例输出 #1

3

提示

数据规模和约定

对于40%的数据，1 ≤ N ≤ 16。

对于100%的数据，1 ≤ N ≤ 10000，1 ≤ M ≤ 100000，-10000 ≤ w , c ≤ 10000。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
int w[10020], x, y, z, ans;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		w[i] *= 2;
	}
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		w[x] += z;
		w[y] += z;
	}
	sort(w + 1, w + 1 + n);
	for (int i = n; i > 0; i -= 2) {
		ans += w[i] - w[i - 1];
	}
	cout << ans / 2 << endl;
	return 0;
}

题解

P4643 [国家集训队]阿狸和桃子的游戏
把边权转换到点权上，贪心

P1265 公路修建

https://www.luogu.com.cn/problem/P1265

题目描述

某国有 $n$ 个城市，它们互相之间没有公路相通，因此交通十分不便。为解决这一“行路难”的问题，政府决定修建公路。修建公路的任务由各城市共同完成。

修建工程分若干轮完成。在每一轮中，每个城市选择一个与它最近的城市，申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。

政府审批的规则如下：

1. 如果两个或以上城市申请修建同一条公路，则让它们共同修建；
2. 如果三个或以上的城市申请修建的公路成环。如下图，A 申请修建公路 AB，B 申请修建公路 BC，C 申请修建公路 CA。则政府将否决其中最短的一条公路的修建申请；
3. 其他情况的申请一律同意。

一轮修建结束后，可能会有若干城市可以通过公路直接或间接相连。这些可以互相连通的城市即组成“城市联盟”。在下一轮修建中，每个“城市联盟”将被看作一个城市，发挥一个城市的作用。

当所有城市被组合成一个“城市联盟”时，修建工程也就完成了。

你的任务是根据城市的分布和前面讲到的规则，计算出将要修建的公路总长度。

输入格式

第一行一个整数 $n$，表示城市的数量。（$n \leq 5000$）

以下 $n$ 行，每行两个整数 $x$ 和 $y$，表示一个城市的坐标。（$-10^6 \leq x,y \leq 10^6$）

输出格式

一个实数，四舍五入保留两位小数，表示公路总长。（保证有惟一解）

样例 #1

样例输入 #1

4
0 0
1 2
-1 2
0 4

样例输出 #1

6.47

提示

修建的公路如图所示：

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
double x[5020], y[5020];
double d[5020];
bool v[5020];
double ans;
double dist(int i, int j) {
	return hypot(x[i] - x[j], y[i] - y[j]);
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	for (int i = 1; i < n; i++) {
		d[i] = 1e30;
	}
	for (int i = 0; i < n; i++) {
		int mini = -1;
		double mind = 1e30;
		for (int j = 0; j < n; j++) {
			if (!v[j]) {
				if (mind > d[j]) {
					mind = d[j];
					mini = j;
				}
			}
		}
		ans += mind;
		v[mini] = true;
		for (int j = 0; j < n; j++) {
			if (!v[j]) {
				d[j] = min(d[j], dist(j, mini));
			}
		}
	}
	cout << fixed << setprecision(2) << ans << endl;
	return 0;
}

题解

P3366 【模板】最小生成树

https://www.luogu.com.cn/problem/P3366

题目描述

如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

输入格式

第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。

接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。

输出格式

如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。

样例 #1

样例输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

样例输出 #1

7

提示

数据规模：

对于 $20\%$ 的数据，$N\le 5$，$M\le 20$。

对于 $40\%$ 的数据，$N\le 50$，$M\le 2500$。

对于 $70\%$ 的数据，$N\le 500$，$M\le 10^4$。

对于 $100\%$ 的数据：$1\le N\le 5000$，$1\le M\le 2\times 10^5$，$1\le Z_i \le 10^4$。

样例解释：

所以最小生成树的总边权为 $2+2+3=7$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[5020];
int n, m;
long long ans;
pair<int, pair<int, int> > a[200020];
int F(int x) {
	if (f[x] == x) {
		return x;
	}
	f[x] = F(f[x]);
	return f[x];
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
	}
	sort(a, a + m);
	for (int i = 0; i < m; i++) {
		int x = F(a[i].second.first);
		int y = F(a[i].second.second);
		if (x != y) {
			f[x] = y;
			ans += a[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

题解

参考代码（Luogu P3366）：

#include <bits/stdc++.h>
using namespace std;
int f[5020];
int n, m;
long long ans;
pair<int, pair<int, int> > a[200020];
int find(int x) {
    return f[x] != x ? f[x] = find(x) : x;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        f[i] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> a[i].second.first >> a[i].second.second >> a[i].first;
        // 读入边的两个端点和边权。
    }
    sort(a, a + m);
    // 按照边权(first)从小到大排序。
    for (int i = 0; i < m; i++) {
        int x = find(a[i].second.first);
        int y = find(a[i].second.second);
        if (x != y) {
        // 如果这条边的左右端点不在同一个集合内，那么选择这条边，并合并他们。
            f[x] = y;
            ans += a[i].first;
        }
    }
    cout << ans << endl;
    return 0;
}

P2121 拆地毯

https://www.luogu.com.cn/problem/P2121

题目背景

还记得 NOIP 2011 提高组 Day1 中的铺地毯吗？时光飞逝，光阴荏苒，三年过去了。组织者精心准备的颁奖典礼早已结束，留下的则是被人们踩过的地毯。请你来解决类似于铺地毯的另一个问题。

题目描述

会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示，其中 u 和 v 为地毯连接的两个关键区域编号，w 为这条地毯的美丽度。

由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留 K 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙算出这 K 条地毯的美丽度之和最大为多少。

输入格式

第一行包含三个正整数 n、m、K。

接下来 m 行中每行包含三个正整数 u、v、w。

输出格式

只包含一个正整数，表示这 K 条地毯的美丽度之和的最大值。

样例 #1

样例输入 #1

5 4 3
1 2 10
1 3 9
2 3 7
4 5 3

样例输出 #1

22

提示

选择第 1、2、4 条地毯，美丽度之和为 10 + 9 + 3 = 22。

若选择第 1、2、3 条地毯，虽然美丽度之和可以达到 10 + 9 + 7 = 26，但这将导致关键区域 1、2、3 构成一个环，这是题目中不允许的。

1<=n,m,k<=100000

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[100020];
int n, m, l;
long long ans;
pair<int, pair<int, int> > a[100020];
int F(int x) {
	if (f[x] == x) {
		return x;
	}
	f[x] = F(f[x]);
	return f[x];
}
int main() {
	cin >> n >> m >> l;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
	}
	sort(a, a + m);
	for (int i = m - 1; i >= 0 && l > 0; i--) {
		int x = F(a[i].second.first);
		int y = F(a[i].second.second);
		if (x != y) {
			l--;
			f[x] = y;
			ans += a[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

题解

P1195 口袋的天空

https://www.luogu.com.cn/problem/P1195

题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数 $N$，再给你 $M$ 个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成 $K$ 个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。

输入格式

第一行有三个数 $N,M,K$。

接下来 $M$ 行每行三个数 $X,Y,L$，表示$X$云和 $Y$ 云可以通过 $L$ 的代价连在一起。

输出格式

对每组数据输出一行，仅有一个整数，表示最小的代价。

如果怎么连都连不出 $K$ 个棉花糖，请输出 No Answer。

样例 #1

样例输入 #1

3 1 2
1 2 1

样例输出 #1

1

提示

对于 $30\%$ 的数据，$N \le 100$，$M \le 10^3$；

对于 $100\%$ 的数据，$1 \le N \le 10^3$，$1 \le M \le 10^4$，$1 \le K \le 10$，$1 \le X,Y \le N$，$0 \le L<10^4$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[5020];
int n, m, l;
long long ans;
pair<int, pair<int, int> > a[200020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main() {
	cin >> n >> m >> l;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
	}
	sort(a, a + m);
	for (int i = 0; i < m; i++) {
		int x = F(a[i].second.first);
		int y = F(a[i].second.second);
		if (x != y) {
			f[x] = y;
			ans += a[i].first;
			n--;
		}
		if (n == l) {
			break;
		}
	}
	if (n == l) {
		cout << ans << endl;
	} else {
		cout << "No Answer" << endl;
	}
	return 0;
}

题解

P1396 营救

https://www.luogu.com.cn/problem/P1396

题目背景

“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 $t$ 区，而自己在 $s$ 区。

该市有 $m$ 条大道连接 $n$ 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 $s$ 至 $t$ 的路线，使得经过道路的拥挤度最大值最小。

输入格式

第一行有四个用空格隔开的 $n$，$m$，$s$，$t$，其含义见【题目描述】。

接下来 $m$ 行，每行三个整数 $u, v, w$，表示有一条大道连接区 $u$ 和区 $v$，且拥挤度为 $w$。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数，代表最大的拥挤度。

样例 #1

样例输入 #1

3 3 1 3
1 2 2
2 3 1
1 3 3

样例输出 #1

2

提示

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n\leq 10$。
• 对于 $60\%$ 的数据，保证 $n\leq 100$。
• 对于 $100\%$ 的数据，保证 $1 \leq n\leq 10^4$，$1 \leq m \leq 2 \times 10^4$，$w \leq 10^4$，$1 \leq s, t \leq n$。且从 $s$ 出发一定能到达 $t$ 区。

---

样例输入输出 1 解释

小明的妈妈要从 $1$ 号点去 $3$ 号点，最优路线为 $1$->$2$->$3$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int f[10020];
int n, m, s, t;
long long ans;
pair<int, pair<int, int> > a[20020];
int F(int x) {
	return f[x] != x ? f[x] = F(f[x]) : x;
}
int main() {
	cin >> n >> m >> s >> t;
	for (int i = 1; i <= n; i++) {
		f[i] = i;
	}
	for (int i = 0; i < m; i++) {
		cin >> a[i].second.first >> a[i].second.second >> a[i].first;
	}
	sort(a, a + m);
	for (int i = 0; i < m; i++) {
		int x = F(a[i].second.first);
		int y = F(a[i].second.second);
		f[x] = y;
		if (F(s) == F(t))
		{
			cout << a[i].first << endl;
			break;
		}
	}
	return 0;
}

题解

加入每条边后判断
if (F(s) == F(t)) print answer, break
可以证明最优解一定是在最小生成树上走

Luogu P3366
Kruskal最小生成树

Luogu P1111
Kruskal求最小生成树最大边

Luogu P2820
Kruskal最小生成树，求所有不选的边的权值之和

Luogu P1547
Kruskal求最小生成树最大边

Luogu P2916
Kruskal求最小生成树，边权需要转化

最小生成树：
2个性质

1. 任意一个环上最大的边一定不在最小生成树上 -> Kruskal
2. 任意一个割上最小的边一定在最小生成树上 -> Prim

时间复杂度
Kruskal 排序 并查集 O(m log m)
Prim 堆优化 O((n + m) log n)
Prim 暴力 O(n^2)

一般情况下 用 Kruskal 最好
特殊情况，比如完全图

MST:

1. minimize the sum of edges
2. minimize the longest edge
3. minimize the second longest edge
4. minimize the third longest edge

Kruskal:

1. sort all edges by length
2. for each edge, try to merge them

Prim:
https://www.luogu.com.cn/problem/P2916
P2916 [USACO08NOV]Cheering up the Cow G
把点权转换到边权上，做最小生成树

http://poj.org/problem?id=3657
P2898 [USACO08JAN]Haybale Guessing G

Kruskal
复杂度排序所有的边 m log m

1. minimize the longest edge
2. minimize the sum of edges
3. minimize the second longest edge

Kruskal

$O(m \log m)$

m is the number of edges

sort the edges,

Merge the two end points of edges by union find set.

The edge with maximum weight in a cycle can't be in MST.

The number of vertices = The number of edges + 1

http://poj.org/problem?id=2395
P1547 [USACO05MAR]Out of Hay S

http://usaco.org/index.php?page=viewproblem2&cpid=946
P5425 [USACO19OPEN]I Would Walk 500 Miles G
MST by Prim, or analysis the properties

P4643 [国家集训队]阿狸和桃子的游戏

$n$ vertices with weight, $n$ is even. $m$ edges with weight.

2 players color the vertices in turn.

Finally, each player will color $n/2$ vertices.

The final score = the sum of vertex weight + the sum of edges whose both vertices are colored by the player.

The first player want to maximize (score of player 1)-(score of player 2)

The second player want to maximize (score of player 2)-(score of player 1)

Add half of the edge weight to the vertex weight

greedy algorithm

http://poj.org/problem?id=1258
P1546 [USACO3.1]最短网络 Agri-Net
MST

P2212 [USACO14MAR]Watering the Fields S
points on a plane, Euclid distance, find MST
segments less than C can't be chosen.

P2872 [USACO07DEC]Building Roads S
points on a plane, Euclid distance, find MST
Some points are already connected

P2916 [USACO08NOV]Cheering up the Cow G
W[j] = 2 * L[j] + C[S[j]] + C[E[j]]
Find the MST

http://poj.org/problem?id=2485
adjacent matrix, find the longest edge in MST.

http://poj.org/problem?id=2560

P1265 公路修建
points on a plane, Euclid distance, find MST
There are $n^2$ edges.
n^2条边不可能都输入

We need some ways to generate the edge weights.
需要一个算法生成这些边权

http://poj.org/problem?id=1789
Truck History
Complete Graph

dist(i, j) = edit distance s[i], s[j]

http://poj.org/problem?id=3723
Conscription
n + m soldiers
To collect a soldier without any privilege, 10000

For edge(x, y, d)
To collect y when x is collected, 10000 - d

Find the minimum cost

最小生成树
既是 边权之和最小的生成树
也是 最大边最小的生成树
也是 次大边最小的生成树

如果是求最小生成森林（不需要最小生成树，可以剩下k个连通块）
也是Kruskal

P3366 【模板】最小生成树
模板题
ans += a[i].first

P1547 [USACO05MAR]Out of Hay S
ans = a[i].first

P2121 拆地毯
最大生成森林

P1195 口袋的天空
最小生成森林

P1967 货车运输
上一个题目的多组询问版
需要先求最大生成树
然后在最大生成树上询问路径最小值

CF609E
和 P1967 几乎一模一样
求最小生成树
对于树边，答案直接是MST的边权和
对于非树边，答案是 选择这条边 删去树上的路径中的最大边。

CF160D

P1111 修复公路
有无解的情况
no solution

P2820 局域网

P2126 Mzc家中的男家丁

P4047 [JSOI2010]部落划分
如果k = 2，那么答案是最小生成树最大边（第n-1小边）
如果k = n，那么答案是距离最近的2个节点，也就是最小生成树的最小边（第n-1大边）
求最小生成树的第k-1大边，也是第n-k+1小边

Prim
P1194 买礼物

P2906 [USACO08OPEN]Cow Neighborhoods G

(x1, y1)
(x2, y2)

|x1 - x2| + |y1 + y2| =

(a1 = x1 + y1, b1 = x1 - y1)
(a2 = x2 + y2, b2 = x2 - y2)

max(|a1 - a2|, |b1 - b2|)

if the points are sorted
max(a1 - a2, b1 - b2) for all b2 <= b1
max(a1 - a2, b2 - b1) for all b2 >= b1

max(a1 - a2, b1 - b2) <= C for all b2 <= b1
max(a1 - a2, b2 - b1) <= C for all b2 >= b1

a1 - a2 <= C && b1 - b2 <= C for all b2 <= b1
a1 - a2 <= C && b2 - b1 <= C for all b2 >= b1

There are n items, the i-th is $a_i$.

If we have the i-th item, we can use $b_{i,j}$ to buy the j-th item.

We want to buy all the items.

What is the minimum cost.