3 条题解

  • 1
    @ 2024-2-1 18:44:15 
    # include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long INF = 0x3f3f3f3f3f3f3f3f;
int n;
long long dist[N], dep[N], pre[N], suf[N], a[N], b[N], c[N], d[N], ans1, ans2;
vector<pair<int, int>> g[N], circle;
bool vis[N], on_circle[N];
bool dfs(int u, int f) {
    if (vis[u]) {
        return true;
    }
    vis[u] = true;
    for (auto e : g[u]) {
        int v = e.first,
            w = e.second;
        if (v == f) {
            continue;
        }
        if (dfs(v, u)) {
            circle.emplace_back(v, w);
            on_circle[v] = true;
            return true;
        }
    }
    return false;
}
pair<int, long long> bfs(int s) {
    int res = s;
    queue<int> q;
    unordered_set<int> set;
    q.emplace(s);
    set.emplace(s);
    dist[s] = 0;
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (auto e : g[u]) {
            int v = e.first, w = e.second;
            if (!vis[v] && !on_circle[v]) {
                dist[v] = dist[u] + w;
                if (dist[v] > dist[res]) {
                    res = v;
                }
                q.emplace(v);
                set.emplace(v);
                vis[v] = true;
            }
        }
    }
    long long dist_res = dist[res];
    for (int u : set) {
        vis[u] = false;
        dist[u] = INF;
    }
    return {res, dist_res};
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;

    for (int i = 1, u, v, w; i <= n; i++) {
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    dfs(1, 0);
    reverse(circle.begin(), circle.end());
    fill(begin(vis), end(vis), false);
    fill(begin(dist), end(dist), INF);
    for (int i = 1; i <= circle.size(); i++) {
        int u = circle[i - 1].first;
        on_circle[u] = false;
        auto o = bfs(u);
        dep[i] = o.second;
        ans1 = max(ans1, bfs(o.first).second);
        on_circle[u] = true;
    }
    for (int i = 2; i <= circle.size(); i++) {
        pre[i] = pre[i - 1] + circle[i - 1].second;
    }
    for (int i = circle.size() - 1; i; i--) {
        suf[i] = suf[i + 1] + circle[i].second;
    }
    for (int i = 1; i <= circle.size(); i++) {
        a[i] = max(a[i - 1], dep[i] + pre[i]);
    }
    for (int i = circle.size(); i; i--) {
        b[i] = max(b[i + 1], dep[i] + suf[i]);
    }
    long long mx = 0;
    for (int i = 1; i <= circle.size(); i++) {
        c[i] = max(c[i - 1], mx + dep[i] + pre[i]);
        mx = max(mx, dep[i] - pre[i]);
    }
    mx = 0;
    for (int i = circle.size(); i; i--) {
        d[i] = max(d[i + 1], mx + dep[i] + suf[i]);
        mx = max(mx, dep[i] - suf[i]);
    }
    ans2 = INF;
    for (int i = 1; i < circle.size(); i++) {
        ans2 = min(ans2, max({a[i] + b[i + 1] + circle[0].second, c[i], d[i + 1]}));
    }
    cout << fixed << setprecision(1) << static_cast<double> (max(ans1, ans2)) / 2 << endl;

    return 0;
}
    • 0
      @ 2023-8-28 10:34:01

      这是luogu上的原文

      题意解读

      你有一颗基环树，现在想让你找一个点，使得这个点（不一定在节点上）到所有点的距离中最大距离最短。

      分析：

      答案即为基环树的直径的一半。

      证明：

      由基环树的直径定义可得：

      直径上的两个端点在基环树上有最长距离（否则就不是直径了）。

      那么如果我们要求某个点到所有点的距离中最大距离最短。

      自然可得在直径的中点处，得最大距离最短。

      证毕。

      解题思路

      接下来就因该看如何实现求直径的操作了。

      对于一颗基环树，其本质上是一颗（或多颗树）+ 环（有却只有一个）构成。

      那么，我们只需把环找出断开并特殊处理，我们就可以把基环树当成树对待。

      （基环树常见套路）。

      代码过程

      代码编译环境： GNU C++ 11

      存图

      我们以链式前向星存边（链式前向星的 uu 可以不要）。

      struct Edge {
	ll u,v,w,nxt;
} edge[MAXN];
ll cnt,head[MAXN];
void AddEdge(ll u,ll v,ll w) {
	edge[++cnt] = {u,v,w,head[u]},head[u] = cnt;
}

      判断环

      定义数组：

      #define ll long long
ll father[MAXN],val[MAXN];
ll ringlength[MAXN],ring[MAXN],ringcnt,ringroot;
bool inring[MAXN];
ll length[MAXN];
ll dfn[MAXN],ct;
      • fatherfather 代表的是在判断环中存贮的对应节点的父节点。
      • valval 对应的是在存图中记录的对应 fatheri→sonifather_{i} \to son_{i} 的边权值。

      （为什么要记录呢？因为在调用时可以更快更方便，且通往这个节点的 fatherifather_{i} 不只是一个，记录下来以防弄错）。

      • ringlengthringlength 表示找到环后对应的边权的大小。
      • ringring 表示环中一个点的编号。
      • ringcntringcnt 表示环中边的数量（同时也是点的数量）。
      • inringinring 则表示是否在环里。
      • lengthlength 则表示子树的深度。
      • ringrootringroot 没有用，芝士忘删了。

      tarjan 判断环

      void dfs(ll x) {
	dfn[x] = ++ct;
	ll v,w;
	for(ll i = head[x]; i; i=edge[i].nxt) {
		v = edge[i].v,w = edge[i].w;
		if(v != father[x]) {
			if(!dfn[v]) {
				val[v] = w,father[v] = x;
				dfs(v);
			} else if(dfn[x] < dfn[v]) {
				for(ll i = v; i != x; i = father[i]) {
					inring[i] = 1,ring[++ringcnt] = i,ringlength[ringcnt]=val[i];
				}
				inring[x] = 1,ring[++ringcnt] = x,ringlength[ringcnt]=edge[i].w;
			}
		}
	}
}

      不会的自行补学一下 tarjan。

      重点解释一下 if 中的内容。

      if(v != father[x]) {
	if(!dfn[v]) {
		val[v] = w,father[v] = x;
		dfs(v);
	} else if(dfn[x] < dfn[v]) {
		for(ll i = v; i != x; i = father[i]) {
			inring[i] = 1,ring[++ringcnt] = i,ringlength[ringcnt]=val[i];
		}
		inring[x] = 1,ring[++ringcnt] = x,ringlength[ringcnt]=edge[i].w;
}

      在没有利用双向边回到自己父亲节点时：

      判断新节点是否被经过。

      如果未被经过，则将边权和将搜的点的 fatherifather_{i} 记录下来。

      边权不会错是应为如果没发现环，回溯过来时边权会重新被覆盖， fatherifather_{i} 数组同理。

      在进一步进行深搜：

      如果发现更晚的时间戳（即证明已经经过），则等价于发现环。

      在由于之前的 fatherifather_{i} 已被记录，最终可以遍历环，把环储存下来（不要忘了自己）。

      统计所有子树最大高度

      ll res1,res2;//统计所有子树最大高度 
void statistics(ll x,ll fa){
	ll v,w;
	for(int i = head[x];i;i = edge[i].nxt){
		v = edge[i].v,w = edge[i].w;
		if(!inring[v]&&v != fa){
			statistics(v,x);
			res1 = max(res1,length[x]+length[v]+w);
			length[x] = max(length[x],length[v]+w);
		}
	}
}

      也是重点解释 if 中的部分：

      if(!inring[v]&&v != fa){
	statistics(v,x);
	res1 = max(res1,length[x]+length[v]+w);
	length[x] = max(length[x],length[v]+w);
}

      如果不在环上，进行搜索，统计一棵子树的最大直径。

      当加上如下代码时：

      for(int i = 1;i <= ringcnt;i++){
	statistics(ring[i],0);
}

      则是统计所有子树的最大直径 res1res1 。

      而 lengthilength_{i} 则表示长度记录，不断更新，获得从这个点下去子树的最大深度。

      准确来讲叫距离，所以叫 lengthlength 。

      重点分割线 qwq

      对于直径的求解

      ll sum,maxx,tmp;
ll A[MAXN],B[MAXN],C[MAXN],D[MAXN];
void init(){
	for(int i = 1;i <= ringcnt;i++){
		sum += ringlength[i-1];
		A[i] = max(A[i-1],length[ring[i]]+sum);
		B[i] = max(B[i-1],sum+maxx+length[ring[i]]);
		maxx = max(maxx,length[ring[i]]-sum);
	}
	sum = maxx = 0;
	tmp = ringlength[ringcnt];
	ringlength[ringcnt] = 0;
	for(int i = ringcnt;i>=1;i--){
		sum += ringlength[i];
		C[i] = max(C[i+1],length[ring[i]]+sum);
		D[i] = max(D[i+1],sum+maxx+length[ring[i]]);
		maxx = max(maxx,length[ring[i]]-sum);
	}
}
init();
res2 = B[ringcnt];
for(int i = 1;i <= ringcnt;i++){
	res2 = min(max(A[i]+C[i+1]+tmp,max(B[i],D[i+1])),res2);
}
printf("%.1f",double(max(res1,res2)/2.0));//注意整除

      我们规定：

      AA 为前缀链长度 + 当前节点子树最大深度。

      BB 为前缀链中两个子树的最大深度 + 两点之间链的长度（距离）。

      CC 为后缀链长度 + 当前节点子树最大深度。

      DD 为后缀中两个子树的最大深度 + 两点之间链的长度（距离）。

      则我们只需要对四种情况考虑即可：

      • Ai+Ci+tmpA_{i}+C_{i}+tmp 表示经过环的断点的直径。
      • BiB_{i} 表示在 ii 左侧的直径的最大值。
      • Di+1D_{i+1} 表示在 ii 右侧的直径的最大值。
      • res1res1 表示在子树中的直径最大值。

      解释：

      这段的计算运用了动规思想。

      lengthringi+sumilength_{ring_{i}}+sum_{i} 表示前缀（后缀）链的长度 + 此时树的深度。

      sumi+maxxi+lengthringisum_{i}+maxx_{i}+length_{ring_{i}} 表示前缀（后缀）链的长度 + 最大子树的深度 maxximaxx_{i} + 此时树的深度。

      maxximaxx_{i} 减去了前缀链的长度，以此来抵消前缀的影响。

      枚举环上的点，看看何时直径最大。

      为什么：这样枚举之间复杂度最坏也是 O(n)O(n) ，而不是两两枚举的 O(n2)O(n^2) 。

      其实就是前缀和（后缀）优化啦。

      完整代码

      #include <bits/stdc++.h>
#define ll long long
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
const int MAXN = 2e5+10;
ll n; 
struct Edge {
	ll u,v,w,nxt;
} edge[MAXN];
ll cnt,head[MAXN];
void AddEdge(ll u,ll v,ll w) {
	edge[++cnt] = {u,v,w,head[u]},head[u] = cnt;
}
ll father[MAXN],val[MAXN];
ll ringlength[MAXN],ring[MAXN],ringcnt,ringroot;
bool inring[MAXN];
ll length[MAXN];
ll dfn[MAXN],ct;
void dfs(ll x) {
	dfn[x] = ++ct;
	ll v,w;
	for(ll i = head[x]; i; i=edge[i].nxt) {
		v = edge[i].v,w = edge[i].w;
		if(v != father[x]) {
			if(!dfn[v]) {
				val[v] = w,father[v] = x;
				dfs(v);
			} else if(dfn[x] < dfn[v]) {
				for(ll i = v; i != x; i = father[i]) {
					inring[i] = 1,ring[++ringcnt] = i,ringlength[ringcnt]=val[i];
				}
				inring[x] = 1,ring[++ringcnt] = x,ringlength[ringcnt]=edge[i].w;
			}
		}
	}
}
ll res1,res2;//统计所有子树最大高度 
void statistics(ll x,ll fa){
	ll v,w;
	for(int i = head[x];i;i = edge[i].nxt){
		v = edge[i].v,w = edge[i].w;
		if(!inring[v]&&v != fa){
			statistics(v,x);
			res1 = max(res1,length[x]+length[v]+w);
			length[x] = max(length[x],length[v]+w);
		}
	}
}
ll sum,maxx,tmp;
ll A[MAXN],B[MAXN],C[MAXN],D[MAXN];
void init(){
	for(int i = 1;i <= ringcnt;i++){
		sum += ringlength[i-1];
		A[i] = max(A[i-1],length[ring[i]]+sum);
		B[i] = max(B[i-1],sum+maxx+length[ring[i]]);
		maxx = max(maxx,length[ring[i]]-sum);
	}
	sum = maxx = 0;
	tmp = ringlength[ringcnt];
	ringlength[ringcnt] = 0;
	for(int i = ringcnt;i>=1;i--){
		sum += ringlength[i];
		C[i] = max(C[i+1],length[ring[i]]+sum);
		D[i] = max(D[i+1],sum+maxx+length[ring[i]]);
		maxx = max(maxx,length[ring[i]]-sum);
	}
}
int main() {
	scanf("%lld",&n);
	ll u,v,w;
	for(int i = 1;i <= n;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		AddEdge(u,v,w);
		AddEdge(v,u,w);
		father[i] = i;
	}
	dfs(1);
	for(int i = 1;i <= ringcnt;i++){
		statistics(ring[i],0);
	}
	init();
	res2 = B[ringcnt];
	for(int i = 1;i <= ringcnt;i++){
		res2 = min(max(A[i]+C[i+1]+tmp,max(B[i],D[i+1])),res2);
	}
	printf("%.1f",double(max(res1,res2)/2.0));//注意整除
	return 0;
}

      后记：感谢管理员大大百忙中审核题解。

      • 0
        @ 2022-7-14 20:10:02 
        #include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>

#define For(i,a,b) for(register int i=a;i<=b;++i)
#define Dwn(i,a,b) for(register int i=a;i>=b;--i)
#define Pn putchar('\n')
#define Re register
#define Db double

using namespace std;

const int N=1e5+5;

int head[N],nxt[N*2],v[N*2],cnt=1;
Db w[N*2],dia[N],z,dmx[N],Fn;
int n,m,x,y;
inline void read(int &v){
	v=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar();
}
inline void read(Db &v){
	v=0;
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar();
}
void add(int ux,int vx,Db wx){
	nxt[++cnt]=head[ux]; head[ux]=cnt; v[cnt]=vx; w[cnt]=wx;
	nxt[++cnt]=head[vx]; head[vx]=cnt; v[cnt]=ux; w[cnt]=wx;
}

int tot=0,top=0,st[N],cr[N*2],vis[N],suc=0,fc[N];
Db crD[N*2],stD[N];
void dfsCir(int x,int fa){
	vis[x]=1;
	if(x==1)st[++top]=x,stD[top]=0;
	for(Re int i=head[x];i;i=nxt[i]){
		int vv=v[i]; if(vv==fa)continue;
		if(!vis[vv]){
			st[++top]=vv; stD[top]=w[i];
			dfsCir(vv,x);
		}else{
			suc=1;
			while(st[top]!=vv){
				fc[st[top]]=1;
				cr[++tot]=st[top];
				crD[tot]=stD[top--];
			}
			fc[st[top]]=1;
			cr[++tot]=st[top];
			crD[tot]=w[i];
			return;
		}
		if(suc)return;
	}
	top--;
}
int pos;
Db mxD;
void dfsTrD(int x,Db dix,int fa){
	if(dix>mxD)mxD=dix,pos=x;
	for(Re int i=head[x];i;i=nxt[i]){
		int vv=v[i];
		if(vv==fa||fc[vv])continue;
		dfsTrD(vv,dix+w[i],x);
	}
}
Db GetTrD(int x){
	pos=mxD=0;
	dfsTrD(x,0,0);
	mxD=0;
	dfsTrD(pos,0,0);
	return mxD;
}

Db pre[N],bck[N],bs1[N],bs2[N],Ds=0; 
void DP(){
	Ds=mxD=0;
 	For(i,1,tot){
 		pre[i]=max(pre[i-1],dmx[cr[i]]+Ds);
 		if(i>=2)bs1[i]=max(bs1[i-1],mxD+Ds+dmx[cr[i]]);
 		mxD=max(mxD,dmx[cr[i]]-Ds);
	 	Ds+=crD[i];
	}
	Ds=mxD=0;
	crD[0]=crD[tot];
	Dwn(i,tot,1){
		bck[i]=max(bck[i+1],dmx[cr[i]]+Ds);
		if(i<=tot-1)bs2[i]=max(bs2[i+1],mxD+Ds+dmx[cr[i]]);
		mxD=max(mxD,dmx[cr[i]]-Ds);
		Ds+=crD[i-1];
	}
	Fn=bs1[tot];
	For(i,1,tot-1){
		Db mx1=max(bs1[i],bs2[i+1]);
		Db mx2=max(mx1,pre[i]+bck[i+1]+crD[0]);
		Fn=min(Fn,max(mx1,mx2));
	}
}

int main(){
	//freopen("ex.in","r",stdin);
//	freopen("ex.out","w",stdout);
    read(n); 
    For(i,1,n){read(x); read(y); read(z); add(x,y,z);}
    dfsCir(1,0); 
    For(i,1,tot){
    	fc[cr[i]]=0;
		dia[cr[i]]=GetTrD(cr[i]);
		fc[cr[i]]=1;
	}
    For(i,1,tot){
    	mxD=0; 
    	dfsTrD(cr[i],0,0);
    	dmx[cr[i]]=mxD;
    } 
    DP();
    For(i,1,tot)Fn=max(Fn,dia[cr[i]]);
    printf("%.1lf",Fn/2.0);
    return 0;
}
        • 1

        [NOI2013] 快餐店

        信息

        ID
        399
        时间
        2000ms
        内存
        500MiB
        难度
        6
        标签
        递交数
        8
        已通过
        5
        上传者
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        2. © 2021-2024 Hydro.ac
        4. Worker 1 in 75ms
        5. Hydro v4.11.2 Professional