最小生成树

对于无向图G(V,E)G(V, E) 的切割(S,VS)(S, V-S) 是集合VV 的一个划分,如果边(u,v)(u, v)
一个端点位于SS,另一个端点位于VSV-S,称为该边横跨切割(S,VS)(S, V-S)

如果集合AA 中不存在横跨切割的边,那么称切割尊重集合AA
在横跨切割的所有边中,权值最小的边称为轻量级边

定理 不妨设集合AAEE 的一个子集,并且AA 包括在图GG 的某棵最小生成树中
设切割(S,VS)(S, V-S) 尊重集合AA,又设(u,v)(u, v) 是横跨切割(S,VS)(S, V-S) 的一条轻量级边
那么边(u,v)(u, v) 对于集合AA 是安全的,可以执行AA{(u,v)}A \leftarrow A \cup \{(u, v)\}

证明,假设原图中的最小生成树为TT,边(u,v)(u, v)TTuvu \to v 的简单路径pp 构成环路
u,vu, v 分别位于切割(S,VS)(S, V-S) 的两端,在pp 中可以找到一条边(x,y)(x, y),使得(x,y)(x, y) 横跨(S,VS)(S, V-S)
因为切割(S,VS)(S, V-S) 尊重集合AA,所以(x,y)A(x, y) \notin A,由此可以构造出新的生成树

T=T{(x,y)}{(u,v)}T' = T - \{(x, y)\} \cup \{(u, v)\}

由于边(u,v)(u, v) 横跨切割(S,VS)(S, V-S) 并且是一条轻量级边,(x,y)(x, y) 也横跨切割,所以
w(u,v)w(x,y)w(u, v) \leqslant w(x, y)

w(T)=w(T)w(x,y)+w(u,v)w(T)w(T') = w(T) - w(x, y) + w(u, v) \leqslant w(T)

TT 是最小生成树,那么TT' 也一定是最小生成树

下面再证明(u,v)(u, v) 是一条安全边,因为ATA \subseteq T 并且(x,y)A(x, y) \notin A,所以
AT{(x,y)}A \subseteq T- \{(x, y)\},由于T=T{(x,y)}{(u,v)}T' = T - \{(x, y)\} \cup \{(u, v)\},所以A{(u,v)}TA \cup \{(u, v)\} \subseteq T'
TT' 是最小生成树,所以(u,v)(u, v) 是安全的

kruskal and prim

kruskal 和 prim 算法都是基于上述思想实现的

Kruskal 算法
kruskal 算法实现起来比较简单

  • 初始化并查集,此时每个点各自是一个集合
  • 将所有的边从小到大排序,扫描每一条边(u,v)(u, v)
  • 如果find(u)=find(v)\text{find}(u) = \text{find}(v),忽略这一条边
    否则的话合并u,vu, v 所在的集合,并且将w(u,v)w(u, v) 累加到答案ans\text{ans}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int maxn = 1e5 + 10;
int n, m, pa[maxn];
struct Edge {
int x, y, z;
} edges[maxn];

int kruskal() {
for (int i = 0; i <= n; i++) pa[i] = i;
function<int(int)> get = [&](int x) {
return x == pa[x] ? x : pa[x] = get(pa[x]);
};

sort(edges+1, edges+1+m, [](const Edge& a, const Edge &b) {
return a.z < b.z;
});

int ans = 0;
for (int i = 1; i <= m; i++) {
int x = get(edges[i].x), y = get(edges[i].y);
if (x == y) continue;
pa[x] = y, ans += edges[i].z;
}
return ans;
}

Prim 算法
Prim 算法需要用到轻量级边的定义,实现过程类似分层图
由于最小生成树有n1n-1 条边,所以需要加入n1n-1 条轻量级边
需要一个d(y)d(y) 数组,当ySy \in S 时,d(y)d(y) 表示(y,x)(y, x) 横跨切割 时,yy 作为起点的最小边权
yTy \in T 时,d(y)d(y) 表示边(x,y)(x, y) 横跨切割时,以yy 作为终点的边的最小边权

  • 维护两个集合S,TS, T,其中SS 是已经确定的最小生成树集合,TT 是剩下的集合
  • 接着执行n1n-1 次循环,添加轻量级边,对于每一次的循环,扫描所有点
    找到不在SS 中的点xx,其中d(x)d(x) 必须是最小的,将其加入集合SS
    之后更新横跨切割的边(x,y)(x, y),即更新xx所有出边,即d(y)=min(d(y),w(x,y))d(y) = \min(d(y), w(x, y))

执行完 Prim 算法之后,i=1nd(i)\displaystyle\sum_{i = 1}^{n} d(i) 才是最小生成树的总权值
因为d(y)d(y) 保存的是每一条横跨切割的轻量级边

时间复杂度为O(n2)O(n^2),主要用于稠密图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void prim() {
memset(d, inf, sizeof d);
memset(inq, 0, sizeof inq);

d[1] = 0;
for (int i = 1; i < n; i++) {
int x = 0;
for (int j = 1; j <= n; j++) {
if (!inq[j] && (x == 0 || d[j] < d[x])) x = j;
}
inq[x] = 1;
for (int y = 1; y <= n; y++) {
if (!inq[y]) d[y] = min(d[y], G[x][y]);
}
}
}

prim 执行完成之后
int res = 0;
for(int i = 1; i <= n; i++) res += d[i];

res 是最小生成树

走廊泼水节
将图扩充为完全图,并且最小生成树不变,假设最小生成树轻量级边的权值为zz
那么添加的边权值应该>z> z 并且尽可能小,添加的边权设为z+1z+1 即可

在执行 kruskal 算法时,对于边(x,y)(x, y),合并xx 所在的集合S(x)S(x)yy 所在集合S(y)S(y)
根据乘法原理,一共有S(x)S(y)S(x) \cdot S(y) 条不同的横跨切割的边,(两个集合任选一个点)
除去最小生成树中的轻量级边保持不变,一共要添加(S(x)S(y)1)(w(x,y)+1)(S(x)\cdot S(y) - 1) \cdot (w(x, y) + 1)
将这个值累加到答案中即可

野餐规划

给定一个无向图,求满足11 号节点的度数不超过给定整数SS

  • 如果去掉11 号节点,并且用dfs\text{dfs} 求出连通块,连通块个数为TT
    T>ST > S 显然无解,因为最小生成树定义必须包括所有节点
    求连通块的时候可以标记节点uu 属于连通块b(u)b(u)
  • 对于每一个连通块cccc,执行calc(cc)\text{calc}(cc),在连通块内部求出最小生成树
    具体来说,执行 kruskal 算法时,只考虑边(x,y)(x, y),满足b(x)=b(y)=ccb(x) = b(y) = cc
    这里还可以求出边(1,u)(1, u),其中uccu \in cc 并且w(1,u)w(1, u) 权值最小
    (1,u)(1, u) 也加入到生成树中

经过以上处理,已经得到了节点11 度数为TT 的最小生成树,在计算的时候,如果(u,v)(u, v) 在生成树中
标记used(u,v)=1\text{used}(u, v) = 1,以上初步得到最小生成树答案为ans\text{ans}

那么剩下STS-T 个点可以和11 连,还可能使得答案更优,对于边(1,x)(1, x),权值为zz
如果(1,x)(1, x) 不在最小生成树中,从11 开始沿着最小生成树路径走到xx,得到最大边权记为maxcost\text{maxcost}
那么ans=ans(maxcostz)\text{ans}' = \text{ans} - (\text{maxcost} - z)
此时可以用(1,x)(1, x) 替换maxcost\text{maxcost} 的边,使得生成树更优
当且仅当maxcostz>0\text{maxcost} - z > 0 并且maxcostz\text{maxcost} - z 尽量大时成立

思路就有了,我们循环执行STS-T 次,对于每一次操作,先对现有生成树执行dfs\text{dfs}
求出1x1 \to x 沿着最小生成树路径走,经过的最大权边maxcost(x)\text{maxcost}(x)(其中xx 不在最小生成树上
然后每次循环执行的时候,尝试添加一条不在原生成树中的边(1,x)(1, x),这样的边应该如何选择呢?
很显然必须选择满足d(x)=maxcost(x)w(1,x)d(x) = \text{maxcost}(x) - w(1, x)d(x)>0d(x) > 0d(x)d(x) 最大的(1,x)(1, x)
ansansdans \leftarrow ans - d,还要记得标记used(1,x)=1\text{used}(1, x) = 1
并且清除maxcost\text{maxcost} 的那条边(u,v)(u, v)used(u,v)=0\text{used}(u, v) = 0
如果能找到的最大的dd<0< 0,直接退出循环

具体到算法实现上,最小生成树经常需要求解如下问题
path:1x\text{path}: 1 \to x 沿着最小生成树路径走,所经过的最大的边,记为maxe[x]\text{maxe}[x]
求解过程是基于动态规划的,dfs(u,maxe)\text{dfs}(u, maxe),对于边(u,v)(u, v)
如果(u,v)(u, v) 在最小生成树路径上,那么检查

  • w(u,v)<maxe[u].zw(u, v) < maxe[u].z,那么maxe[v]maxe[u]maxe[v] \leftarrow maxe[u]
  • w(u,v)>=maxe[u].zw(u, v) >= maxe[u].z,更新maxe[v]=Edge{u,v,w(u,v)}maxe[v] = Edge\{u, v, w(u, v)\}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<Edge> maxe(maxn);
vector<int> vis(maxn);
void dfs(int u, vector<Edge>& maxe) {
vis[u] = 1;
for (auto v : G[u]) {
if (!used[u][v] || vis[v]) continue;

if (g[u][v] < maxe[u]) maxe[v] = maxe[u];
else maxe[v] = Edge{u, v, g[u][v]};

dfs(v, maxe);
}
}

调用之前记得清空 maxe 和 vis

0-1分数规划问题

0-1 分数规划问题可以用小数二分来求解,具体来看
最优比率生成树

每条边有成本CeC_e 和长度LeL_e,求生成树TT 满足eTCeeTLe\displaystyle \frac{\displaystyle\sum_{e\in T} C_e}{\displaystyle\sum_{e\in T}L_e} 取到最小值

实际上可以二分答案,其实就是求满足eTCeeTLemid\displaystyle \frac{\displaystyle\sum_{e\in T} C_e}{\displaystyle\sum_{e\in T}L_e} \geqslant mid 恒成立midmid
其中l=0,r=Mmax{Ce}Mmin{Le}l = 0, r = \displaystyle\frac{M \cdot \max\{C_e\}}{M \cdot \min\{L_e\}},所以r=1000.0r = 1000.0,然后进行小数二分

算法执行的过程如下,二分要满足eTCemideTLe\displaystyle\sum_{e\in T}C_e \geqslant mid \cdot \sum_{e \in T}L_e
实际上对于每条边,有CemidLe0C_e - mid \cdot L_e \geqslant 0,建图的时候,只需要把每条边的权值设为CemidLeC_e - mid \cdot L_e 即可
二分的判断过程如下

  • 如果CemidLe0\sum C_e - mid \cdot \sum L_e \geqslant 0,实际上等价于CemidLe\sum C_e - mid \cdot \sum L_e 最小值都要0\geqslant 0
    在图上执行最小生成树prim(mid)0\text{prim}(mid) \geqslant 0,此时midmid 是一个可行解,并且尝试继续增大midmid,令l=midl = mid
  • 否则的话,令r=midr = mid,二分结束后,ll 就是答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cassert>

using namespace std;

#define fill_v(f, v) fill(f.begin(), f.end(), v)

const int maxn = 1000 + 10;
const double inf = 3e8;
const double eps = 1e-6;
int n;

struct V {
double x, y, h;
};
vector<V> v(maxn, V());
double gRe[maxn][maxn], gLe[maxn][maxn];

inline double dist(int i, int j) {
return sqrt( (v[i].x-v[j].x)*(v[i].x-v[j].x) + (v[i].y-v[j].y)*(v[i].y-v[j].y) );
}

bool prim(double mid) {
vector<double> d(maxn, inf);
vector<int> inq(maxn, 0);

d[1] = 0;
for (int i = 0; i < n-1; i++) {
int x = 0;
for (int j = 1; j <= n; j++) {
if (!inq[j] && (x == 0 || d[j] < d[x])) x = j;
}
inq[x] = 1;

for (int y = 1; y <= n; y++) {
if (!inq[y] && d[y] > gRe[x][y] - mid * gLe[x][y] + eps) d[y] = gRe[x][y] - mid * gLe[x][y];
}
}
double ans = 0.0;
for (int i = 1; i <= n; i++) {
assert(d[i] != inf);
ans += d[i];
}
return ans >= 0 ? 1 : 0;
}

void solve() {
double l = 0.0, r = 1000.0;
while (l + eps < r) {
double mid = (l + r) / 2.0;
if (prim(mid)) l = mid;
else r = mid;
}
printf("%.3lf\n", l);
}

void init() {
fill_v(v, V());
memset(gRe, 0, sizeof gRe), memset(gLe, 0, sizeof gLe);
}

int main() {
//freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
init();
for (int i = 1; i <= n; i++) {
double x, y, z;
scanf("%lf%lf%lf", &x, &y, &z);
v[i] = V{x, y, z};
}

// build
for (int i = 1; i <= n; i++) {
for (int j = i+1; j <= n; j++) {
double Re = abs(v[i].h - v[j].h);
double Le = dist(i, j);

gRe[i][j] = gRe[j][i] = Re;
gLe[i][j] = gLe[j][i] = Le;
}
}

// solve
solve();
}
}

最短路径生成树

黑暗城堡

不难想到这是一个最短路树问题,从源点11 开始执行dijkstra\text{dijkstra} 并且得到距离向量f[]f[\cdots]
(x,y)(x, y) 是最短路树上的边当且仅当f(y)=f(x)+e(x,y)f(y) = f(x) + e(x, y)

可以根据prim\text{prim} 算法的思想,设计出如下算法

  • 根据点i[1n]i \in [1\cdots n]f(i)f(i) 排序,一开始令集合TT 中只有一个元素11,即inq(1)=1\text{inq}(1) = 1
  • 枚举所有的节点x[1n]\forall x \in [1\cdots n],找到第一个不在TT 中的节点xx,即inq(x)=0\text{inq}(x) = 0 的点,并初始化cnt=0cnt = 0
    接下来需要统计出TT 中有多少个点pp 满足d(x)=d(p)+(p,x)d(x) = d(p) + (p, x),满足的话就令cnt++cnt++
  • 根据乘法原理,令res=rescntres = res \cdot cnt,然后把xx 加入TT 中,即inq(x)=1\text{inq}(x) = 1
    执行完之后,resres 就是答案

子图的最小生成树

北极网络

如果没有通信卫星的话,那么很显然DD 是原图G=(N,M)G = (N, M) 最小生成树中权值最大的边

现在有SS 个通信卫星,实际上是求GG 的一个子图G=(NS)G' = (N-S),即子图中有NSN-S 个点
同时还必须满足子图GG'生成树TT' 尽量小,生成树中权值最大的边就是所求的DD

最小生成树证明中,有一个结论
G(N,M)G(N, M) 的最小生成树,一定包括权值最小的N1N-1 条边
那么子图GG' 的最小生成树一定包括最小的NS1N-S-1 条边

可以这么设计算法,执行kruskal\text{kruskal} 的时候,对边从小到大排序,并初始化cnt=0cnt = 0,当并查集xyx \neq y
pa[x]=y, cnt++pa[x] = y, \ cnt++,当cnt=NScnt = N-S 的时候,此时边ee 的权值就是答案

说明,此时维护的子图有NSN-S 个节点,有NS1N-S-1 条边,另外还需要一条边连到“带有卫星的节点”
即子图外的节点,所以总共是最小的NSN-S 条边

四叶草魔杖

根据1N161 \leqslant N \leqslant 16,很容易想到这一定是一个状态压缩
00 表示宝石还未被处理,11 表示已经被处理,那么起始状态为(000)(00\cdots 0),终态为(111)(11\cdots 1)
S=(1n)1S = (1 \ll n) - 1,从dp(0)dp(S)dp(0) \to dp(S)dp(S)dp(S) 就是答案

涉及枚举子集的操作,比如枚举SS 的子集S0S_0,代码如下

1
2
3
4
5
6
7
for (int S = 1; S < (1<<n); S++) {
dp[S] = 初始化
for (int S0 = S; S0; S0 = (S0-1) & S) {
dp[S] = max(dp[S], dp[S^S0] + f(S0))
// 其中 f(S0) 是将 S0 并入集合中的代价
}
}

回到该问题,对于某一状态SS,它之前的状态假设为SS',那么要考虑SSS' \to S 新加入了哪些元素?
刚刚加入的元素一定是SS 的一个子集,可以考虑枚举子集S0S_0,状态转移方程如下
dp(S)=min(dp(S),dp(SS0)+f(S0))dp(S) = \min (dp(S), dp(S \oplus S_0) + f(S_0)),其中f(S0)f(S_0) 是将S0S_0 并入集合的最小代价

接下来需要考虑f(S0)f(S_0) 怎么求,首先S0S_0 必须合法,也就是说新加入的元素iiiAi=0\sum_{i} A_i = 0
这很简单,对S0S_0 中为11 的每一位iisum=iAisum = \displaystyle\sum_{i} A_i
如果sum=0sum = 0 才合法,否则的话不合法

S0S_011 的位取出来,假设有CC 个为11 的位,求出这些位能量转移的最小代价,就是f(S0)f(S_0)
而这又是一个部分点的最小生成树问题,只需要将mm 条边按权值排序,然后依次检查每一条边
对于边(x,y)(x, y),只有S0S_0 中表示x,yx, y 的位同时为11 的时候,将边权值累加到结果中
另外注意,累加的时候记得统计生成树边的个数cntcnt,只有cnt=C1cnt = C-1 的时候才合法

至此,先预处理f(S)f(S),然后执行dpdpdp((1n)1)dp((1 \ll n)-1) 就是答案