问题描述:求无向图中直径最小的生成树
定义:图上的某个在节点或边上的点,使得到该点最远的点的距离最小。根据 图的绝对中心 的定义可以知道,到绝对中心距离最远的结点至少有两个,且这两个最远点经过中心点的最短路是最小直径生成树的直径。
求解方法:设 d [ i ] [ j ] d[i][j] d[i][j] 表示图中节点 i , j i,j i,j 之间的最短路。 r k [ i ] [ j ] rk[i][j] rk[i][j] 表示到点 i i i 第 j j j 远的点。
如图, d [ c ] [ i ] = min ( d [ u ] [ i ] + x , d [ v ] [ i ] + ( w − x ) ) d[c][i]=\min(d[u][i]+x,d[v][i]+(w-x)) d[c][i]=min(d[u][i]+x,d[v][i]+(w−x))。
d [ c ] [ i ] d[c][i] d[c][i] 关于 x x x 的函数图像如下图所示,是由两个斜率绝对值相等的线段构成。
对该边上的点 c c c 到图上所有点的最短距离关于 c c c 在边上的位置,即 f ( x ) = max i ∈ [ 1 , n ] d [ c ] [ i ] f(x)=\max\limits_{i\in[1,n]}d[c][i] f(x)=i∈[1,n]maxd[c][i] 的图像作图,显然最低点对应的 c c c 点的位置是图的绝对中心的候选点之一。
现在问题转化为如何求函数的最小值。
设 a n s ans ans 为最小直径生成树的直径。
首先对于绝对中心在节点上的情况,更新 a n s = min i ∈ [ 1 , n ] ( a n s , d [ i ] [ r k [ n ] ] ⋅ 2 ) ans=\min\limits_{i\in[1,n]}(ans,d[i][rk[n]]\cdot 2) ans=i∈[1,n]min(ans,d[i][rk[n]]⋅2),即到图上到该点最短距离最大的点的距离的两倍。
对于绝对中心在边上的情况,做出 f ( x ) f(x) f(x) 图像如下图,发现当且仅当存在距离该边的某一端点 u u u 距离相大小邻的两个点 i 1 , i 2 i_1,i_2 i1,i2 使得 d [ u ] [ i 1 ] < d [ u ] [ i 2 ] d[u][i_1]<d[u][i_2] d[u][i1]<d[u][i2] 且 d [ v ] [ i 1 ] > d [ v ] [ i 2 ] d[v][i_1]>d[v][i_2] d[v][i1]>d[v][i2] 时针对两点 i 1 , i 2 i_1,i_2 i1,i2 的最短距离图像的交点的函数值为函数 f ( x ) f(x) f(x) 的极小值。枚举这样的极小值就可以得到绝对中心在边上的情况的候选点。
综合两种情况就可以得到图的绝对中心即最小直径生成树的直径 a n s ans ans 了。
时间复杂度 O ( n 3 log n ) O(n^3\log n) O(n3logn) 。
模板:
const int N = 1005;
struct MDST {
int d[N][N], n, m, tot;
int rk[N][N];
struct Edge {
int x, y, z;
} e[(N * N) >> 1];
inline void floyd() {
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
inline void add(int x, int y, int z) {
if (d[x][y] <= z)return;
e[++tot] = {
x, y, z};
d[x][y] = d[y][x] = z;
}
inline void solve() {
memset(d, 0x3f, sizeof(d));
n = qr(), m = qr();
for (int i = 1; i <= n; i++)d[i][i] = 0;
while (m--) {
int x = qr(), y = qr(), z = qr();
add(x, y, z);
}
floyd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)rk[i][j] = j;
sort(rk[i] + 1, rk[i] + n + 1, [&](int x, int y) {
return d[i][x] < d[i][y]; });
}
int ans = INF;
for (int i = 1; i <= n; i++)ans = min(ans, d[i][rk[i][n]] * 2);
for (int i = 1; i <= tot; i++)
for (int j = n - 1, k = n; j >= 1; j--)
if (d[e[i].y][rk[e[i].x][j]] > d[e[i].y][rk[e[i].x][k]])
ans = min(ans, d[e[i].x][rk[e[i].x][j]] + d[e[i].y][rk[e[i].x][k]] + e[i].z), k = j;
printf("%d\n", ans);
}
} M;
以绝对中心为起点,生成一棵最短路径树。
模板:
完全图Dijkstra换成 O ( n 2 ) O(n^2) O(n2) 版。
const int N = 205;
struct MDST {
int g[N][N], n, m, tot;
int rk[N][N], d[N][N];
int fa[N];
struct Edge {
int x, y, z;
} e[(N * N) >> 1];
struct {
int x, y;
double d;
} key;
inline void floyd() {
memcpy(d, g, sizeof(d));
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
inline void add(int x, int y, int z) {
if (g[x][y] <= z)return;
e[++tot] = {
x, y, z};
g[x][y] = g[y][x] = z;
}
double dis[N];
bool v[N];
struct node {
int x;
double d;
inline bool operator<(node a) const {
return d > a.d;
}
};
priority_queue<node> q;
inline void dijkstra() {
for (int i = 1; i <= n; i++)dis[i] = 1e18;
memset(v, false, sizeof(bool) * (n + 1));
if (key.y) {
q.push({
key.x, key.d});
dis[key.x] = key.d;
q.push({
key.y, g[key.x][key.y] - key.d});
dis[key.y] = g[key.x][key.y] - key.d;
} else q.push({
key.x, 0}), dis[key.x] = 0;
while (!q.empty()) {
node t = q.top();
q.pop();
if (v[t.x])continue;
v[t.x] = true;
for (int y = 1; y <= n; y++)
if (dis[y] > t.d + g[t.x][y]) {
fa[y] = t.x;
dis[y] = t.d + g[t.x][y];
q.push({
y, dis[y]});
}
}
for (int i = 1; i <= n; i++)
if (fa[i]) printf("%d %d\n", i, fa[i]);
if (key.y) printf("%d %d\n", key.x, key.y);
}
/*void dijkstra() {
for (int i = 1; i <= n; i++)dis[i] = 1e18;
memset(v, false, sizeof(bool) * (n + 1));
dis[key.x] = key.d;
if (key.y)dis[key.y] = g[key.x][key.y] - key.d;
for (int i = 1; i < n; i++) {
int x = 0;
for (int j = 1; j <= n; j++)
if (!v[j] && (x == 0 || dis[j] < dis[x])) x = j;
v[x] = true;
for (int y = 1; y <= n; y++)
if (dis[y] > dis[x] + g[x][y])fa[y] = x, dis[y] = dis[x] + g[x][y];
}
for (int i = 1; i <= n; i++)
printf("%d %d\n", i, fa[i]);
if (key.y) printf("%d %d\n", key.x, key.y);
}*/
inline void solve() {
memset(g, 0x3f, sizeof(g));
n = qr(), m = qr();
for (int i = 1; i <= n; i++)g[i][i] = 0;
while (m--) {
int x = qr(), y = qr(), z = qr();
add(x, y, z);
}
floyd();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++)rk[i][j] = j;
sort(rk[i] + 1, rk[i] + n + 1, [&](int x, int y) {
return d[i][x] < d[i][y]; });
}
int ans = INF;
for (int i = 1; i <= n; i++)
if (ans > d[i][rk[i][n]] * 2) {
ans = d[i][rk[i][n]] * 2;
key = {
i, 0, 0};
}
for (int i = 1; i <= tot; i++)
for (int j = n - 1, k = n; j >= 1; j--)
if (d[e[i].y][rk[e[i].x][j]] > d[e[i].y][rk[e[i].x][k]]) {
int len = d[e[i].x][rk[e[i].x][j]] + d[e[i].y][rk[e[i].x][k]] + e[i].z;
k = j;
if (ans <= len)continue;
key = {
e[i].x, e[i].y, (1.0 * len) / 2 - d[e[i].x][rk[e[i].x][j]]};
ans = len;
}
printf("%d\n", ans);
dijkstra();
}
} M;
文章浏览阅读101次。链接:http://pan.baidu.com/s/1eSqSY8E密码:yqaf转载于:https://www.cnblogs.com/wordblog/p/6804750.html_白色博客网站
文章浏览阅读705次。java-poi、excel操作_java 对excel 数据汇总
文章浏览阅读152次。给定一个Excel表格中的列名称,返回其相应的列序号。例如,A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28 ...示例 1:输入: “A”输出: 1示例 2:输入: “AB”输出: 28示例 3:输入: “ZY”输出: 701其实就是26进制转10进制class Solution {public: int titleToNumber(string s) { int_计算excel的列序号c++
文章浏览阅读729次。Bug fix release : otp_src_R15B01Build date : 2012-04-02This is R15B01, the first maintenance release for the R15B major release.You can find the README file for the release at http_otp_src_r15b01.tar.gz
文章浏览阅读2.7k次,点赞2次,收藏3次。在上篇文章《[哈希值和可变性Hash value and mutability](https://blog.csdn.net/wumingxiaoyao/article/details/108912543)》最后说到 set 去重问题,所以这篇主要是通过实践来研究一下 set 去重背后的故事,当然也是参考了网上一些资料得到了一些启发,感谢那些陌生的喜欢分享的博友们。想了解更多 Python 基础序列文章,请参考 [Python 基础系列大纲](https://blog.csdn.net/wumingxia_python set 底层如何去掉重复元素原理 数组去重
文章浏览阅读3.9k次,点赞6次,收藏37次。你好_r语言grf包
文章浏览阅读4.3k次。关注『AI科技大本营』的各位小伙伴,新年好!营长祝愿大家天天都是18岁!跟放假休息的各位一样,元旦假期的营长着实也不想干活……想起前两天刚刚更新的《黑镜》第四季还没有跟,营长便决定在新年的第一天恶补一下科技和AI的黑暗面。第1集,《联邦星舰卡利斯特号》:“柯克船长”——咳,一直被老板和同事精神虐待的游戏公司老码农,却拥有一台能通过DNA来复制意识的机器,于是老码农变身猥琐男,把老板和同事的意识上传_黑镜鳄鱼的眼泪
文章浏览阅读3.4k次。耳机有两颗麦克风,一颗在顶部,一颗在末端底部,顶部的用来拾取环境噪音,底部的用来拾取通话。在嘈杂的环境中,两颗麦克风拾取的噪音将会反向叠加用来抵消噪音降噪。实际通话过程中,确实非常有效,官方给出的数据是时速30公里/小时的风噪可正常通话,可见其实力非凡。..._双麦克风降噪原理
文章浏览阅读1.3k次,点赞35次,收藏26次。在现代Web架构中,NGINX以其高性能、稳定性和灵活性而广受青睐。本文将深入探讨NGINX中的两个核心功能:URL重写和反向代理,以帮助您更好地理解和配置这些强大的特性。_nginx set指令
文章浏览阅读2.3w次,点赞27次,收藏138次。HTTP1.0、HTTP2.0、HTTP 3.0及HTTPS简要介绍1 HTTP1.0及HTTPSHTTP 建立之初,是为了将超文本标记语言(HTML)文档从Web服务器传送到客户端的浏览器。但随着CSS,Javascript的出现,以及移动互联时代的到来,我们不得不对HTTP进行不断地优化。HTTP优化:影响一个 HTTP 网络请求的因素主要有两个方面:带宽和延迟。随着网络基础建设的完善,带宽因素已经不需要再考虑,仅需要考虑的就是延迟。延迟主要受三个方面影响:浏览器阻塞(HOL blocking_http1.0
文章浏览阅读1.8k次。ros与arduino串口通信c++写在最前安装serial库编写arduino串口通信程序编写ros节点端口号配置配置CmakeLists.txt文件编译整个ROS工程运行节点后记写在最前串口通信在嵌入式领域的重要性我也就不多说了, 这里的ros与arduino串口通信的方案, 同样适合于stm32, 51单片机等各种芯片. 这里与rosserial有区别, rosserial是基于某种类..._c++ rosserial
文章浏览阅读6.3k次,点赞11次,收藏44次。高频面经汇总:https://blog.csdn.net/qq_40262372/article/details/1160755288.1Spring相关 面试题总结8.1.1什么是Spring框架?Spring是一种轻量级开发框架,旨在提高开发人员的开发效率以及系统的可维护性。目的:解决企业应用开发的复杂性功能:使用基本的JavaBean代替EJB,并提供了更多的企业应用功能范围:任何Java应用简单来说,Spring是一个轻量级的控制反转(IoC)和面向切..._spring,springmvc,springboot面试题