环球旅行 图论 —— 直径
题目链接
作者：rhapHsody
题目描述：
有n个点由n-1条边连通，若去掉一条边，则图中的直径最小是多少。
输入描述：
第一行一个正整数n（n<=106），表示点的数量。并将这些点从1到n编号。
接下来n-1行，每行三个正整数a,b,w。表示编号为a的点和编号为b的点之间有一条长度为w（w<=1000）的边。
输出描述：
输入一行一个整数，满足题中要求。
为了使去掉一条边后直径最小，我们一定会选择把原图直径上的某条边去掉。枚举去掉直径上每条边并更新最小值，需要注意的是每次枚举我们还要计算直径，肯定会时间超限，所以我们就要想办法把这些直径提前得到并储存起来。
接下来就是解决问题的方法： 首先，要掌握一般求解直径的两种方法（两次dfs，树形dp） 方法一：两次dfs （补充：这个方法可以得到直径的两端点 L , R）#include
#include
#include
using namespace std;
const int N = 1e5 + 1;
struct edge { //链式前向星
int to, next, w; edge(){}
edge(int a,int b,int c):to(a),next(b),w(c){}
}e[N << 1]; int tot, head[N];
int d[N];// 记录节点到根的距离
void dfs(int x, int pre, int &lr) {
if (d[lr] < d[x]) lr = x;
for(int i = head[x]; i != -1; i = e[i].next) {
int to = e[i].to;
if (to == pre) continue;
d[to] = d[x] + e[i].w;
dfs(to, x, lr);
}
}
int main() {
int n; scanf("%d", &n);
memset(head, -1, sizeof(head));
for(int i = 1; i < n; ++i) {
int x,y,k; scanf("%d%d%d", &x, &y, &k);
e[++tot]=edge(y,head[x],k),head[x]=tot;
e[++tot]=edge(x,head[y],k),head[y]=tot;
}
int l,r; dfs(1,0,l=1); d[l]=0;dfs(l,0,r=l);
printf("%d\n", d[r]);
return 0;
}
方法二：树形DP （补充：可以得到所有子树的直径）
#include
#include
#include
using namespace std;
const int N = 1e5 + 1;
struct edge { //链式前向星
int to, next, w; edge(){}
edge(int a,int b,int c):to(a),next(b),w(c){}
}e[N << 1]; int tot, head[N];
int f1[N], f2[N];// 以i为根的直径和最长链
void dp(int x, int pre) {// 树形dp
for(int i = head[x]; i != -1; i = e[i].next) {
int to = e[i].to;
if (to == pre) continue;// 防止回头
dp(to, x);
f1[x] = max(f1[x], max(f1[to], f2[x] + f2[to] + e[i].w));
if (f2[x] < f2[to] + e[i].w) f2[x] = f2[to] + e[i].w;
}
}
int main() {
int n; scanf("%d", &n);
memset(head, -1, sizeof(head));
for(int i = 1; i < n; ++i) {
int x,y,k; scanf("%d%d%d", &x, &y, &k);
e[++tot]=edge(y,head[x],k),head[x]=tot;
e[++tot]=edge(x,head[y],k),head[y]=tot;
}
dp(1, 0); printf("%d\n", f1[1]);
return 0;
}
根据两种方法的补充，我们可以把它们结合起来，以 L 为根记录它所有子树的直径，同理再 R 为根记录它的所有子树的直径，最后在我们进行枚举的时候就可以直接判断并更新直径。具体代码如下：
#include
#include
#include
using namespace std;
const int N = 1e6+1;
const int inf = 0x3f3f3f3f;
template inline void read(T &x,int xk=10) { // quick read
char ch = getchar();T f = 1;
for(x =0;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') f=-1;
for(;ch='0';ch=getchar()) x=x*xk+ch-'0';x*=f;
}
struct edge { //链式前向星
int to, next, w; edge(){}
edge(int a,int b,int c):to(a),next(b),w(c){}
}e[N << 1]; int tot, head[N];
int d[N],f1[N],f2[N],D[N],res = inf;
void dfs(int x, int pre, int &lr) {
if (d[lr] < d[x]) lr = x;
for(int i = head[x]; i != -1; i = e[i].next) {
int to = e[i].to;
if (to == pre) continue;
d[to] = d[x] + e[i].w;
dfs(to, x, lr);
}
}
void dpl(int x, int pre) {
for(int i = head[x]; i != -1; i = e[i].next) {
int to = e[i].to;
if (to == pre) continue;
dpl(to, x);
f1[x]=max(f1[x],max(f1[to],f2[x]+f2[to]+e[i].w));
if (f2[x]<f2[to]+e[i].w) f2[x] = f2[to] + e[i].w;
if (D[x] < f1[x]) D[x] = f1[x];
}
}
void dpr(int x, int pre) {
for(int i = head[x]; i != -1; i = e[i].next) {
int to = e[i].to;
if (to == pre) continue;
dpr(to, x);
f1[x]=max(f1[x],max(f1[to],f2[x]+f2[to]+e[i].w));
if (f2[x]<f2[to]+e[i].w) f2[x] = f2[to] + e[i].w;
if (D[pre] D[x]) res = D[x];
return true;
}
}
return false;
}
int main() {
int n; read(n);
memset(head, -1, sizeof(head));
for(int i = 1; i < n; ++i) {
int x, y, k; read(x); read(y); read(k);
e[++tot]=edge(y,head[x],k),head[x]=tot;
e[++tot]=edge(x,head[y],k),head[y]=tot;
}
int l, r; dfs(1, 0, l = 1); d[l] = 0; dfs(l, 0, r = l);
dpl(l,0);memset(f1,0,sizeof(f1));memset(f2,0,sizeof(f2));dpr(r,0);
Dfs(l, 0, r); printf("%d\n", res);
return 0;
}
作者：rhapHsody
