【SDOI2011 第2轮 DAY1】消防 -[树的直径+树链剖分][解题报告]

【SDOI2011 第2轮 DAY1】消防

题面:

SDOI2011 第2轮 DAY1】消防
时间限制 : 20000 MS 空间限制 : 565536 KB
问题描述

时限\(2s\)
　　某个国家有\(n\)个城市，这\(n\)个城市中任意两个都连通且有唯一一条路径，每条连通两个城市的道路的长度为\(zi(zi<=1000)\)。
　　这个国家的人对火焰有超越宇宙的热情，所以这个国家最兴旺的行业是消防业。由于政府对国民的热情忍无可忍（大量的消防经费开销）可是却又无可奈何（总统竞选的国民支持率），所以只能想尽方法提高消防能力。
　　现在这个国家的经费足以在一条边长度和不超过\(s\)的路径（两端都是城市）上建立消防枢纽，为了尽量提高枢纽的利用率，要求其他所有城市到这条路径的距离的最大值最小。
　　你受命监管这个项目，你当然需要知道应该把枢纽建立在什么位置上。

输入格式

输入包含\(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
【样例输入2】
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3

样例输出

【样例输出1】
5
【样例输出2】
5

提示

【数据规模和约定】
对于\(20\%\)的数据，\(n<=300\)。
对于\(50\%\)的数据，\(n<=3000\)。
对于\(100\%\)的数据，\(n<=300000\)，边长小等于\(1000\)。

题解:

最大值最小?二分答案?然而并不是这样写的;
本题采用贪心的做法;
显然我们选择的枢纽是在树的直径上的,而在这个基础上,我们希望我们选择的路径在合法的情况下尽量长;
于是我们用左右两个指针\(L,R\)从\(Pos[Root1]\)到\(Pos[Root2]\)移动,在移动的过程中,用L所指的节点到\(Root1\)的距离与\(R\)所指节点到\(Root2\)的距离以及\(L、R\)之间的点中,到直径外最大的距离这三者取\(max\)更新答案,保证答案最小;
对于第三个量,我们可以枚举直径上的起点,由于每个点显然最多遍历一次,所以预处理时间复杂度\(O(N)\),单调队列维护区间最大值就可以了;
因为偷懒,写了个树剖维护直径的\(DFS\)序连续,直接就变成在区间上扫一遍;

\(code:\)

#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#define lowbit(x) (x&-x)
#define ll long long
#define ld double
#define mod 998244353 
using namespace std;

char buf[1<<20],*p1,*p2;
inline char gc()
{
//    return getchar();
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin))==p1?0:*p1++;
}

template
inline void read(T &x)
{
    char tt;
    bool flag=0;
    while(!isdigit(tt=gc())&&tt!='-');
    tt=='-'?(flag=1,x=0):(x=tt-'0');
    while(isdigit(tt=gc())) x=x*10+tt-'0';
    if(flag) x=-x;
}

struct node{
    int x,len;
    inline node(int a=0,int b=0)
    {x=a,len=b;}
};

const int maxn=300002;
int n,s,root1,root2,mx;
int w[maxn],son[maxn];
int dfn[maxn],tot,pos[maxn];
int sum[maxn],id[maxn],q[maxn];
vectorG[maxn];

void dfs1(int x,int pre,ll dis)
{	
    for(int i=G[x].size()-1;i>=0;i--)
    {
        int p=G[x][i].x;
        int len=G[x][i].len;
        if(p==pre) continue;
        dfs1(p,x,dis+len);
        if(mx=0;i--)
    {
        int p=G[x][i].x;
        int len=G[x][i].len;
        if(p==pre) continue;
        w[p]=len;dfs2(p,x,dis+len);
        if(mxw[son[x]]) son[x]=p;
    }
    w[x]+=w[son[x]];
}

void dfs3(int x,int pre)
{
    dfn[++tot]=x,pos[x]=tot;
    if(!son[x]) return;
    dfs3(son[x],x);
    
    for(int i=G[x].size()-1;i>=0;i--)
    {
        int p=G[x][i].x;
        if(p==pre||p==son[x]) continue;
        dfs3(p,x); 
    }
}

void dfs(int x,int pre,int dis)
{
	mx=max(mx,dis);
	for(int i=G[x].size()-1;i>=0;i--)
	{
		int p=G[x][i].x,len=G[x][i].len;
		if(p==pre||(pos[p]<=pos[root2]&&pos[p]>=pos[root1])) continue;
		dfs(p,x,dis+len);
	}
}

int head,tail;
int ans=1e9;
void modify(int x,int p)
{
	while(tail>=head&&q[tail]<=x) tail--;
	q[++tail]=x;id[tail]=p;
}

int main()
{
//	freopen("1.txt","r",stdin);
//	freopen("2.txt","w",stdout);
    read(n),read(s);
    for(int i=1;i<=n-1;i++)
    {
        int x,y,z;
        read(x),read(y),read(z);
        G[x].push_back(node(y,z));
        G[y].push_back(node(x,z));
    }
    dfs1(1,1,0);mx=0;
    dfs2(root1,root1,0);
    memset(w,0,sizeof(w));
    dfs3(root1,root1);
    for(int i=pos[root1];i<=pos[root2];i++)
    mx=0,dfs(dfn[i],0,0),w[dfn[i]]=mx;
//    for(int i=1;i<=n;i++) printf("%d ",w[i]);
    int l,r;
	l=r=pos[root1];
    while(l<=pos[root2])
    {
    	while(id[head]
树上问题数据结构贪心

相关

数据结构--栈（C语言实现）

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

数据结构+java中常用的集合类

数据结构 之二叉树

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

数据结构与算法之PHP排序算法（冒泡排序）

03java算法与数据结构------环形队列代码实现

算法第四章《贪心策略》上机实践报告

Redis | 第一部分：数据结构与对象 上篇《Redis设计与实现》

数据结构 -- 004.1 串的基本概念

标签