题解 P3761 【[TJOI2017]城市】
getchar123 · · 题解
这题可以O(
暴力枚举删掉的边，使它分成两棵树，然后考虑连接哪两个点可以使最大交通费用最小
这时有两种情况：
1.要最大交通费用的两个点在同一棵树上
2.最大费用的两个点分别在两棵树上
第一种情况是不会被连接的边影响的，我们要想办法连边让第二种情况的最大费用最小。显然是连接两棵树上直径的中点（这里别的题解都讲得比较详细，就不再赘述了）
重点来了：如何优化到O(n)
回顾O（
反证：（此时a->d为原树上直径，b->e为要删的边）假设x1>x2，那么x1+y+z>x2
+y+z，则原树上直径为c->d，与条件矛盾。所以a距离b最远，a为新树上半径一端
得证优化后的时间复杂度依然达不到O（n），继续优化剩下一遍bfs：
(橙色为截掉的边，绿色为直径，左边蓝色为遍历到的点右边红色为遍历一遍的点，紫色为重复遍历的点)可以看到，在枚举删边时有很多点被重复遍历到了。可以考虑第二次只遍历红色部分。这样总共只将树遍历了一遍，可以达到O（n）。
遍历到叶节点时更新直径（为了表述方便，所有边长度为1）（左边新树直径4，右边6）
维护直径中点
求出直径后，要寻找直径中点，此时如果遍历直径求中点，在极端情况下，时间复杂度还是O（
讲解瞎说时间到此结束
下面来梳理一遍思路
- 求出原树上直径，记端点为r，l
- 从直径左侧开始
- 在直径上截边，遍历新增子树，更新直径
- 上一次的中点后移，作为这一次中点
- 更新半径
- 存储信息
- 重复步骤3-6，直到遍历完整个直径
- 右侧同理
- 扫描所有存储的信息，求出最终答案
代码
#include<bits/stdc++.h>
using namespace std;
struct bbbb{
int to,nextt,xx;
}b[10010];
int n,tail,dd[5010],dis[5010],vis[5010],ldd,rdd,diss[5010],ttll;
struct llbb{
int xxx,x;
}lb[5010];
struct cccc{
int zjcd,bjcd,zd;
}cc1[5010],cc2[5010];
void jb(int x,int y,int z){
tail++;
b[tail].nextt=dd[x];
b[tail].to=y;
b[tail].xx=z;
dd[x]=tail;
return;
}
queue<int>q;
void bfs(int x){
memset(vis,0,sizeof(vis));
dis[x]=0;
vis[x]=1;
q.push(x);
while(q.empty()==false){
int xx=q.front();q.pop();
for(int i=dd[xx];i!=0;i=b[i].nextt){
if(vis[b[i].to]==0){
vis[b[i].to]=1;
dis[b[i].to]=dis[xx]+b[i].xx;
q.push(b[i].to);
}
}
}
return;
}
bool dfs(int x,int mb){
if(x==mb){
ttll++;
lb[ttll].x=x;
return true;
}
for(int i=dd[x];i!=0;i=b[i].nextt){
if(vis[b[i].to]==0){
vis[b[i].to]=1;
if(dfs(b[i].to,mb)==true){
ttll++;
lb[ttll].x=x;
lb[ttll].xxx=b[i].xx;
return true;
}
}
}
return false;
}
int bfs1(int x){
int maxx=0;
q.push(x);
while(q.empty()==false){
int xx=q.front();q.pop();
maxx=max(maxx,diss[xx]);
for(int i=dd[xx];i!=0;i=b[i].nextt){
if(vis[b[i].to]==0){
vis[b[i].to]=1;
diss[b[i].to]=diss[xx]+b[i].xx;
q.push(b[i].to);
}
}
}
return maxx;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
jb(x,y,z);
jb(y,x,z);
}
bfs(1);
for(int i=1;i<=n;i++){
if(dis[ldd]<=dis[i]){
ldd=i;//左端点
}
}
bfs(ldd);
for(int i=1;i<=n;i++){
if(dis[rdd]<=dis[i]){
rdd=i;//右端点
}
}
memset(vis,0,sizeof(vis));
vis[ldd]=1;
dfs(ldd,rdd);//存储树的直径
//-------------上面是树的直径部分-----------------
memset(vis,0,sizeof(vis));
for(int i=1;i<=ttll;i++){
vis[lb[i].x]=1;
}
int zhongd=1;
for(int i=2;i<=ttll;i++){
diss[lb[i].x]=diss[lb[i-1].x]+lb[i].xxx;
int qwq=bfs1(lb[i].x);//遍历新子树
if(qwq<=cc1[lb[i-1].x].zjcd){
cc1[lb[i].x]=cc1[lb[i-1].x];
}
else{
while(zhongd<i&&max(diss[lb[zhongd].x],qwq-diss[lb[zhongd].x])>max(diss[lb[zhongd+1].x],qwq-diss[lb[zhongd+1].x])){
zhongd++;//中点后移
}
cc1[lb[i].x].zjcd=qwq;//更新直径
cc1[lb[i].x].bjcd=max(diss[lb[zhongd].x],qwq-diss[lb[zhongd].x]);//更新半径
}
}
memset(vis,0,sizeof(vis));
memset(diss,0,sizeof(diss));
for(int i=1;i<=ttll;i++){//右侧同理
vis[lb[i].x]=1;
}
zhongd=ttll;
for(int i=ttll-1;i>=1;i--){
diss[lb[i].x]=diss[lb[i+1].x]+lb[i+1].xxx;
int qwq=bfs1(lb[i].x);
if(qwq<=cc2[lb[i+1].x].zjcd){
cc2[lb[i].x]=cc2[lb[i+1].x];
}
else{
while(zhongd>i&&max(diss[lb[zhongd].x],qwq-diss[lb[zhongd].x])>max(diss[lb[zhongd-1].x],qwq-diss[lb[zhongd-1].x])){
zhongd--;
}
cc2[lb[i].x].zjcd=qwq;
cc2[lb[i].x].bjcd=max(diss[lb[zhongd].x],qwq-diss[lb[zhongd].x]);
}
}
int minn=1e9;
for(int i=1;i<ttll;i++){//扫描,求出最终答案
minn=min(minn,max(cc1[lb[i].x].bjcd+cc2[lb[i+1].x].bjcd+lb[i+1].xxx,max(cc1[lb[i].x].zjcd,cc2[lb[i+1].x].zjcd)));
}
printf("%d",minn);
return 0;
}-end-
p.s.如果哪里不是很清楚，欢迎私信提建议哦~