[NOI2013]快餐店

C++(g++ 7.5.0) 解法, 执行用时: 67ms, 内存消耗: 23424K, 提交时间: 2023-02-10 16:52:44

#include <bits/stdc++.h>

using ll = long long;

void solve() {
	int n;
	std::cin >> n;

	std::vector<std::vector<std::pair<int, int>>> e(n);

	for (int i = 0; i < n; ++ i) {
		int u, v, w;
		std::cin >> u >> v >> w;
		u --, v --;
		e[u].emplace_back(v, w);
		e[v].emplace_back(u, w);
	}

	std::vector<int> fa(n), cost(n), dfn(n);
	int ts = 0;

	std::vector<int> cyc, val;
	std::vector<bool> st(n);

	{
		std::function<void(int)> dfs = [&](int u) -> void {
			dfn[u] = ++ ts;
			for (auto [v, w] : e[u]) {
				if (v == fa[u]) {
					continue;
				}

				fa[v] = u;
				cost[v] = w;

				if (!dfn[v]) {
					dfs(v);
				}
				else if (dfn[v] < dfn[u]) {
					int p = v;
					do {
						st[p] = true;
						cyc.push_back(p);
						val.push_back(cost[p]);
						p = fa[p];
					} while (p != v);
				}
			}
		};

		dfs(0);
	}

	ll ans = 0;

	std::vector<ll> dist(n);

	{
		std::function<void(int, int)> dfs = [&](int u, int fa) -> void {
			for (auto [v, w] : e[u]) {
				if (v == fa || st[v]) {
					continue;
				}
				dfs(v, u);
				ans = std::max(ans, dist[u] + dist[v] + w);
				dist[u] = std::max(dist[u], dist[v] + w);	
			}
			
		};

		for (auto u : cyc) {
			dfs(u, -1);
		}
	}


	ll sum = 0, max = dist[cyc[0]];
	int m = cyc.size();
	std::vector<ll> A(m), B(m), C(m), D(m);
	A[0] = dist[cyc[0]];
    B[0] = dist[cyc[0]];


	for (int i = 1; i < m; ++ i) {
		auto j = cyc[i];
		sum += val[i - 1];
		A[i] = std::max(A[i - 1], sum + dist[j]);
		B[i] = std::max(B[i - 1], max + sum + dist[j]);
		max = std::max(max, dist[j] - sum);
	}

	sum = 0, max = dist[cyc[m - 1]];
	C[m - 1] = dist[cyc[m - 1]];
    D[m - 1] = dist[cyc[m - 1]];

	for (int i = m - 2; i >= 0; -- i) {
		auto j = cyc[i];
		sum += val[i];
		C[i] = std::max(C[i + 1], sum + dist[j]);
		D[i] = std::max(D[i + 1], max + sum + dist[j]);
		max = std::max(max, dist[j] - sum);
	}	

	ll ans2 = std::max(B[m - 1], D[0]);
	for (int i = 0; i < m - 1; ++ i) {
		auto res = std::max(B[i], D[i + 1]);
		res = std::max(res, A[i] + C[i + 1] + val[m - 1]);
		//std::cerr << A[i] + C[i + 1] + val[0] << " " << B[i] << " " << C[i] << " " << D[i] << "\n";
		ans2 = std::min(res, ans2);
	}

	ans = std::max(ans, ans2);

	std::cout << std::fixed << std::setprecision(1);
	std::cout << ans / 2.0 << "\n";

}

int main() {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	solve();

	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 63ms, 内存消耗: 16540K, 提交时间: 2022-10-05 18:06:26

#include<bits/stdc++.h>
#define int long long
#define qq 12345678
using namespace std;
struct NODE{int id,dis;}cir[qq];
struct EDGE{int to,nxt,val;}edge[qq];
int head[qq],tot=1,m=0,dep[qq],maxn,pos,pre[qq],suf[qq],a[qq],b[qq],c[qq],d[qq];
bool vis[qq],used[qq],iscir[qq];
void add(int x,int y,int z){edge[++tot].to=y,edge[tot].val=z,edge[tot].nxt=head[x],head[x]=tot;}
bool find_circle(int x){
    vis[x]=1;
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].to,z=edge[i].val;
        if(used[i])continue;
        if(vis[y]){iscir[y]=1,cir[++m]=(NODE){y,z};return 1;}
        used[i]=used[i^1]=1;
        if(find_circle(y)){iscir[y]=1,cir[++m]=(NODE){y,z};return 1;}
    }
    return 0;
}
void dfs(int x,int father,int dist){
    if(dist>maxn) maxn=dist,pos=x;
    for(int i=head[x];i;i=edge[i].nxt){
        int y=edge[i].to,z=edge[i].val;
        if(y==father || iscir[y])continue;
        dfs(y,x,dist+z);
    }
}
signed main(){
    int n,x,y,z;
    cin>>n;
    for(int i=1;i<=n;++i){scanf("%lld %lld %lld",&x,&y,&z);add(x,y,z),add(y,x,z);}
    find_circle(1);
    int ans1=0,ans2=1e18;
    for(int i=1;i<=m;++i)x=cir[i].id,iscir[x]=0,maxn=0,dfs(x,0,0),dep[i]=maxn,maxn=0,dfs(pos,0,0),ans1=max(ans1,maxn),iscir[x]=1;
    for(int i=2;i<=m;++i) pre[i]=pre[i-1]+cir[i-1].dis;
    for(int i=m-1;i>=1;--i) suf[i]=suf[i+1]+cir[i].dis;
    for(int i=1;i<=m;++i) a[i]=max(a[i-1],pre[i]+dep[i]);
    for(int i=m;i>=1;--i) b[i]=max(b[i+1],suf[i]+dep[i]);
    maxn=0;
    for(int i=1;i<=m;++i) c[i]=max(c[i-1],maxn+dep[i]+pre[i]),maxn=max(maxn,dep[i]-pre[i]);
    maxn=0;
    for(int i=m;i>=1;--i) d[i]=max(d[i+1],maxn+dep[i]+suf[i]),maxn=max(maxn,dep[i]-suf[i]);
    for(int i=1;i<m;++i) ans2=min(ans2,max(a[i]+b[i+1]+cir[m].dis,max(c[i],d[i+1])));
    double ans=(double)max(ans1,ans2)/2;
    printf("%.1lf",ans);
    return 0;
}

详情