- 任意一颗最小生成树可以包含权值最小的一条边
- 生成树可以包含连接各个联通块的权值最小的边
无向图才可以使用最小生成树算法
1146. 新的开始 - AcWing题库
建立一个超级发电站（虚拟源点），将点权转化为边权。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 330;
int n;
int dist[N], w[N][N];
bool st[N];
int prim()
{
memset(dist, 0x3f, sizeof dist);
dist[0] = 0;//最大边
int res = 0;
for(int i = 0; i < n + 1; i ++ )//加入n+1个点
{
int t = -1;
for(int j = 0; j <= n; j ++ )
if(!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
res += dist[t];
for(int j = 0; j <= n; j ++ )
dist[j] = min(dist[j], w[t][j]);
}
return res;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++ )
{
cin >> w[0][i];
w[i][0] = w[0][i];
}
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n; j ++ )
cin >> w[i][j];
cout << prim();
}
1145. 北极通讯网络 - AcWing题库
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 510, M = N * N / 2;
int n, m, k;
struct edge
{
int a, b;
double w;
}edges[M];
PII q[M];
int f[N];
double get_dist(PII t1, PII t2)
{
double dx = t1.x - t2.x;
double dy = t2.y - t1.y;
return sqrt(dx * dx + dy * dy);
}
int find(int x)
{
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
bool cmp(edge t1, edge t2)
{
return t1.w < t2.w;
}
int main()
{
cin >> n >> k;
for(int i = 0; i < n; i ++ ) f[i] = i;
for(int i = 0; i < n; i ++ ) cin >> q[i].x >> q[i].y;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < i; j ++ )
{
edges[m ++] = {i, j, get_dist(q[i], q[j])};
}
sort(edges, edges + m, cmp);
int cnt = n;
double res = 0;
for(int i = 0; i < m; i ++ )
{
if(cnt <= k) break;
int a = find(edges[i].a), b = find(edges[i].b);
double w = edges[i].w;
if(a != b)
{
f[a] = b;
cnt --;
res = w;
}
}
printf("%.2lf", res);
}
346. 走廊泼水节 - AcWing题库
做法：初始时先将每一个点看成一个大小为$1$的连通块，这个连通块就可以看成一个完全图(因为只有一个点)
做Kruskal算法，在每循环到一条可以合并两个连通块的边$e$时，记$e$的边长为$w$,为了形成一个完全图，就要使得两个已经是完全图的连通块中的点有边，但是为了使最后的唯一最小生成树还是原来那棵而且，新增的边一定要大于$w$：
-
假设新边小于w，因为新增边后会成环，当断开边e，形成的树大小会变小，即不是原来那棵，所以不成立
-
假设新边等于w，同样的断开e，会形成一个大小一样但结构不一样的树，不满足唯一，所以也不成立。
所以只要在每次新增e的时候，给两个连通块内的点增加w+1长的边即可。
- 证明：得出来的完全图中的最小生成树是原来那棵。(反证法)
假设最后生成的完全同中的最小生成树不是原来那棵，在原树中，从小到大遍历n-1条边，找出第一条不在新最小生成树中的边，在新树中将它连上，会形成一个环，由之前加边时的操作可以知道，在这个环中一定存在一条长度大于它的边，断开这更大条，会形成一个更小的树，那就不是最小生成树，所以假设不成立。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 6100;
int f[N], s[N], t, n;
struct edge
{
int a, b, c;
bool operator < (const edge&rhs) const
{
return c < rhs.c;
}
}e[N];
int find(int x) // 并查集
{
if(f[x] == x) return x;
return f[x] = find(f[x]);
}
int main()
{
cin >> t;
while(t --)
{
int sum = 0;
cin >> n;
for(int i = 1; i < n; i ++ )
{
int a, b, c;
cin >> a >> b >> c;
e[i] = {a, b, c};
}
for(int i = 1; i <= n; i ++ ) f[i] = i, s[i] = 1;
sort(e + 1, e + 1 + n - 1);
for(int i = 1; i < n; i ++ )
{
int a = e[i].a, b = e[i].b, c = e[i].c;
//a和b合并
a = find(a);
b = find(b);
if(a != b) //a和b没有合并
{
f[a] = b;
sum += (s[a] * s[b] - 1) * (c + 1);
s[b] += s[a];//加到父亲节点
}
}
cout << sum << endl;
}
}
