P2491 消防
题目描述
某个国家有n个城市，这n个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为zi(zi<=1000)。
这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。
现在这个国家的经费足以在一条边长度和不超过s的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。
你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。
输入输出格式
输入格式：
输入包含n行：
第1行，两个正整数n和s，中间用一个空格隔开。其中n为城市的个数，s为路径长度的上界。设结点编号以此为1，2，……，n。
从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。例如，“2 4 7”表示连接结点2与4的边的长度为7。
输出格式：
输出包含一个非负整数，即所有城市到选择的路径的最大值，当然这个最大值必须是所有方案中最小的。
说明
【数据规模和约定】
对于20%的数据，n<=300。
对于50%的数据，n<=3000。
对于100%的数据，n<=300000，边长小等于1000。
对于消防局的建设的地点，选择在树的直径上是最优的。
树的直径：树中的最长简单路
- 证明：
假设消防局为黄链(A)（(A)不在(D)上），其中有点(A_1)，(A_2)......(A_n)，树的某一直径为蓝链(D)，两边的点分别为(D_1),(D_2)
则对于点(A_i)来说，在整颗树中最远的点即为(D_1)或(D_2)
证明(证明中的证明)：
假设存在(S_2)使得(D_3)距离Ai最远，则必有(S_2+S_1>S_4)(或(S_3))，即产生了新的直径，不成立，得证。
由以上可知，黄链上的点到外面最远的一个点的距离为
(Dis=min{E(A_i,D_1),E(A_i,D_2),iin[1,n]})
若令(dis)最小，则链(A)必在链(D)上。
但是，当(A)在(D)上时，链(A)到外面的点（即不在直径上的点）的距离(f)是可能大于(dis)的，是合法的。
这样是否矛盾？
不矛盾，因为任何一个在外面的链(A)的(dis)都是大于在直径上的链(A)的(f)的
其实不太严谨哈
那么对于这个题，我们就有了思路啊
-
2次dfs求出树的直径（第一次求出某条直径端点，第二次直接抽出直径）
-
预处理直径上每个点(i)向外延伸的最长距离(c[i])
-
对于待检验链(A)，左端为(A_i),右端为(A_j)，此时的最长距离即为(max{E(A_1,A_i),E(A_j,A_n),c[k],kin[i,j]})
前两个好弄，前缀和就行。
后一个是(RMQ)问题，(ST)表线段树维护一下就行。
但还有个更优的，我们注意到我们相当于拿一个窗口划过了链(A),对啊，妥妥的单调队列维护啊
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N=300010;
int n,s;
int used[N];
struct node1
{
int i,w;
node1(){}
node1(int i,int w)
{
this->i=i;
this->w=w;
}
};
deque <node1> q;
struct node
{
int i,w;
node(){}
node(int i,int w)
{
this->i=i;
this->w=w;
}
};
vector <node > g[N];
int l,m_max=0;
int son[N],ww[N];
int c[N];//节点i外面的最长边
void dfs0(int now,int len)
{
used[now]=true;
if(m_max<len)
{
m_max=len;
l=now;
}
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].i,w=g[now][i].w;
if(!used[v])
dfs0(v,w+len);
}
}
void dfs1(int now)
{
used[now]=true;
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].i,w=g[now][i].w;
if(!used[v])
{
dfs1(v);
if(ww[v]+w>ww[now])
{
ww[now]=ww[v]+w;
son[now]=v;
}
}
}
}
int dfs(int now)
{
int mmax=0;
used[now]=1;
for(int i=0;i<g[now].size();i++)
{
int v=g[now][i].i,w=g[now][i].w;
if(!used[v])
mmax=max(dfs(v)+w,mmax);
}
return mmax;
}
int a[N],f[N];
int main()
{
cin>>n>>s;
int u,v,w;
for(int i=1;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
node tt(v,w);
g[u].push_back(tt);
tt.i=u;
g[v].push_back(tt);
}
memset(used,0,sizeof(used));
dfs0(1,0);//找到左端点
memset(used,0,sizeof(used));
memset(son,0,sizeof(son));
memset(ww,0,sizeof(ww));
dfs1(l);//存储直径
memset(used,0,sizeof(used));
int now=l;
int cnt=0;
while(now)
{
used[now]=1;
a[++cnt]=now;
now=son[now];
}
now=l;
cnt=0;
while(now)
{
c[++cnt]=dfs(now);
now=son[now];
}
for(int i=1;i<=cnt;i++)
f[i]=ww[a[i]];
int ans=0x3f3f3f3f,ll=1;
for(int i=1;i<=cnt;i++)
{
node1 tt(i,c[i]);
while(!q.empty()&&c[i]>q.front().w) q.pop_front();
q.push_front(tt);
while(f[ll]-f[i]>s)
{
ll++;
if(q.back().i<ll)
q.pop_back();
}
ans=min(ans,max(f[1]-f[ll],max(f[i],q.back().w)));
}
cout<<ans<<endl;
return 0;
}
结论：
- 两遍DFS求树的直径
- 权有上界的 以最小代价联通整个树的 链在树的直径上
2018.4.27