望月Asta
2022-01-04 17:55:39
NOI2021 都考了 LGV 引理,那以后难道没有那么一点 (?) 可能考最小直径生成树呢?
直径是图中所有最短路径的最大值。
最小直径生成树问题 :
给定一个
求一个生成树使得树的直径最小。
首先引入 图的绝对中心.
图的绝对中心 是使得任何点到该中心最短路径中最大值最小的 位置.
因为绝对中心不一定是某个结点,也可以在一条边上。
然后很
然后可以发现这句话似乎只对树成立,不过后一条 一定有至少两个到绝对中心最远的点 ,这句是没问题的。
具体点 ?
3 3
1 2 1
1 3 1
2 3 1
一个环。
如果直接求图直径除以
那换个想法,考虑直接枚举。
假设绝对中心在边
然后在这条边上尝试移动目前选择的中点的位置,可以发现画出距离
那么就是需要在这些折线里找到最小的就能得到绝对中心了。
类似这样一种感觉 :
然后可以发现这个过程经常需要快速取距离某个点最远的结点这样的操作。
于是定义
可以
然后是具体的算法流程。
全源最短路 (
求
枚举点作为绝对中心
枚举边上的位置作为绝对中心,从最远的向最近找,直到出现转折点,
总体复杂度基本就是巨大常数
CF266D BerDonalds
Code :
struct Edge {
int st,ed,w;
}e[M];
int n,m;
int dis[N][N];
int rnk[N][N];
int val[N];
inline bool cmp(int a,int b) {
return val[a] < val[b];
}
void Centro() {
rep(k,1,n) rep(i,1,n) rep(j,1,n)
dis[i][j] = std::min(dis[i][j],dis[i][k] + dis[k][j]);
rep(i,1,n) {
rep(j,1,n) {
rnk[i][j] = j;
val[j] = dis[i][j];
}
std::sort(rnk[i] + 1,rnk[i] + n + 1,cmp);
}
int ans = INF;
rep(i,1,n)
ans = std::min(ans,dis[i][rnk[i][n]] * 2);
rep(i,1,m) {
int u = e[i].st,v = e[i].ed,w = e[i].w;
int pos = n;
repb(i,n - 1,1) if(dis[v][rnk[u][i]] > dis[v][rnk[u][pos]]) {
ans = std::min(ans,dis[u][rnk[u][i]] + dis[v][rnk[u][pos]] + w);
pos = i;
}
}
write_db(ans / 2.0,2),enter;
}
首先求出绝对中心。
然后分类讨论 :
从该点向外求最短路树即可。
考虑在那条边上建一个虚拟结点,分别向那条边两个端点连边,然后求最短路径树,输出时不输出虚拟节点即可。
SP735 MDST - Minimum Diameter Spanning Tree
SP1479 PT07C - The GbAaY Kingdom
没有代码,因为我发现,求解最小直径生成树是在绝对中心不假,但是求最短路径树似乎是错的……
参见这篇论文
等我看懂了就到 OI-wiki 上去 Pull Request 吧...