NC20574. [SDOI2011]消防
描述
输入描述
输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。
输出描述
输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。
示例1
输入:
5 2 1 2 5 2 3 2 2 4 4 2 5 3
输出:
5
示例2
输入:
8 6 1 3 2 2 3 2 3 4 6 4 5 3 4 6 4 4 7 2 7 8 3
输出:
5
C++(g++ 7.5.0) 解法, 执行用时: 197ms, 内存消耗: 23164K, 提交时间: 2023-02-14 21:49:24
#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#define ll long long
#define reg register
#define fo(a,b,c) for(reg int a=b;a<=c;a++)
#define re(a,b,c) for(reg int a=b;a>=c;a--)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
queue<ll> q;
inline ll gi(){
ll x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
struct io
{
ll u,v,w;
}node[600005];
ll head[300005],dis[300005],pre[300005],ji,ma,zj,yj,vis[300005],po[300005],md,cnt,su[300005],sum;
void dfs(ll u,ll fa,ll ty)
{
for(ll i=head[u];i;i=node[i].u)
{
ll v=node[i].v;
if(v==fa) continue;
dis[v]=dis[u]+node[i].w;
if(ty) pre[v]=u;
dfs(v,u,ty);
}
}
void dfs1(ll u,ll fa)
{
for(ll i=head[u];i;i=node[i].u)
{
ll v=node[i].v;
if(v==fa) continue;
if(vis[v]) dis[v]=0;
else dis[v]=dis[u]+node[i].w;
dfs1(v,u);
}
md=max(md,dis[u]);
}
void add(ll u,ll v,ll w)
{
cnt++;
node[cnt].u=head[u];
node[cnt].v=v;
node[cnt].w=w;
head[u]=cnt;
}
int main()
{
ll n,s;
n=gi(),s=gi();
fo(i,1,n-1)
{
ll x,y,z;
x=gi(),y=gi(),z=gi();
add(x,y,z);
add(y,x,z);
}
dfs(1,0,0);
fo(i,1,n)
{
if(dis[i]>ma)
{
ma=dis[i];
ji=i;
}
}
zj=ji;
dfs(ji,0,1);
ma=0;
fo(i,1,n)
{
if(dis[i]>ma)
{
ma=dis[i];
ji=i;
}
}
ll bj=0;
yj=ji;
ll now=yj;
vis[now]=1;
// cout<<yj<<" "<<zj<<'\n';
while(now!=zj)
{
for(ll i=head[now];i;i=node[i].u)
{
ll v=node[i].v;
if(v!=pre[now]) continue;
sum+=node[i].w;
bj++;
po[bj]=node[i].w;
}
now=pre[now];
vis[now]=1;
}
memset(dis,0,sizeof(dis));
dfs1(yj,0);
ll zma=0,yma=sum;
ma=sum;
ji=1;
fo(i,1,bj)
{
zma+=po[i];
yma-=po[i];
if(max(yma,zma)<ma)
{
ma=max(yma,zma);
ji=i+1;
}
su[i]=su[i-1]+po[i];
}
// cout<<ji<<" ";
ll ans=sum;
ll l=ji,r=ji;
yma=su[bj]-su[ji-1];
zma=su[ji-1];
while(1)
{
if(zma<yma)
{
if(s<po[r]) break;
yma-=po[r];
s-=po[r];
r++;
}
else
{
if(s<po[l-1]) break;
zma-=po[l-1];
s-=po[l-1];
l--;
}
if(yma==0&&zma==0) break;
}
// cout<<md<<" "<<max(yma,zma);
cout<<max(md,max(yma,zma));
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 150ms, 内存消耗: 12424K, 提交时间: 2020-09-17 11:51:30
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=3e5+5,Inf=1e9;
struct Edge{int to,w,nxt;}e[N<<1];
int n,s,fst[N],tote,md,pos,u,v,t,dia[N],tp,fa[N],upw[N],len[N],now,dis[N];
bool od[N];
multiset<int>ms;
void adde(int u,int v,int w){e[++tote]=(Edge){v,w,fst[u]};fst[u]=tote;}
void dfs(int u,int f,int d){
fa[u]=f;if(d>md)md=d,pos=u;
for(int i=fst[u],v,w;i;i=e[i].nxt){
v=e[i].to;w=e[i].w;
if(v!=f)upw[v]=w,dfs(v,u,d+w);
}
}
void dfs2(int u,int f){
len[now]=max(len[now],dis[u]);
for(int i=fst[u],v,w;i;i=e[i].nxt){
v=e[i].to;w=e[i].w;
if(v!=f&&!od[v])dis[v]=dis[u]+w,dfs2(v,u);
}
}
void init(){
dfs(1,0,0);u=pos;md=0;dfs(u,0,0);t=v=pos;
while(t!=u)dia[++tp]=t,t=fa[t];dia[++tp]=u;
}
int pre[N],suf[N],pd[N],que[N],ans=Inf;
int main(){
scanf("%d%d",&n,&s);
for(int i=1,u,v,w;i<n;i++)scanf("%d%d%d",&u,&v,&w),adde(u,v,w),adde(v,u,w);
init();
for(int i=1;i<=tp;i++)od[dia[i]]=true;
for(int i=1;i<=tp;i++)now=i,dfs2(dia[i],0);
for(int i=1,mal=0,nowl=0;i<=tp;i++)
mal=max(mal,len[i]-nowl),pre[i]=mal+nowl,nowl+=upw[dia[i]],pd[i+1]=pd[i]+upw[dia[i]];
for(int i=tp,mal=0,nowl=0;i;i--)
mal=max(mal,len[i]-nowl),suf[i]=mal+nowl,nowl+=upw[dia[i-1]];
//for(int i=1;i<=tp;i++)printf("%d%c",dia[i]," \n"[i==tp]);
//for(int i=1;i<=tp;i++)printf("%d %d %d\n",pre[i],suf[i],pd[i]);
for(int i=1,l=1,hd=1,tl=0;i<=tp;i++){
while(hd<=tl&&len[que[tl]]<len[i])tl--;
que[++tl]=i;
while(pd[i]-pd[l]>s){
while(hd<=tl&&que[hd]<=l)hd++;
l++;
}
ans=min(ans,max(len[que[hd]],max(suf[i],pre[l])));
}
printf("%d\n",ans);
return 0;
}