BZOJ4326: NOIP2015 运输计划

ゝ一世哀愁。 2021-12-23 06:01 306阅读 0赞

题目大意：给出一棵带边权的树和m条路径，可以将一条边的边权变成0，求问最长的路径最短是多少。

题解：

暴力算法：将每条边变不变，用数据结构维护，更新答案。

这样显然过不掉。

通常最值问题考虑贪心和二分答案，这里我们使用二分答案，二分最长的路径是多少。

假如最长路径maxn<=当前二分的值mid，那么结果显然可行。

如果maxn-mid可以通过将一条边的边权变成0来消去，即这条边的边权>=maxn-mid，那么结果也可行。

现在问题转化成：路径长度>mid的所有路径中，是否存在一条公共边，满足这条公共边的边权>=maxn-mid。

如何判断公共边呢？我们记一下每条边经过的次数，如果经过次数等于路径数，则说明这条边是公共边。

经过次数用树上查分来维护就好。

可是你会发现你会被卡常。。。

在这里给出几个优化的方法：

1.快速读入。

2.缩小l和r的范围，由于只能将一条边的边权变成0，所以左边界是最长路径maxn-最大边权tmp，右边界就是最长路径maxn。

3.有很多时间是花费在求LCA上，预处理出每条路径两个端点的LCA。

当然还有更毒瘤的优化方式，这里就不一一赘述了。

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<string>
    #include<map>
    #include<iostream>
    #include<queue>
    using namespace std;
    #define isNum(a) (a>='0'&&a<='9')
    #define SP putchar(' ')
    #define EL putchar('\n')
    #define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
    template<class T1>void read(T1 &r_e_a_d);
    template<class T1>void write(T1 w_r_i_t_e);
    int n,m,len,x,y,z,from[300005],to[300005],head[300005];
    struct EDGE{
    	int to,next,num;
    }edge[600005];
    void add(int u,int v,int w){
    	++len;
    	edge[len].to=v;
    	edge[len].next=head[u];
    	edge[len].num=w;
    	head[u]=len;
    }
    int fa[300005],dep[300005],son[300005],siz[300005],dist[300005];
    void dfs1(int u,int father){
    	fa[u]=father;dep[u]=dep[father]+1;siz[u]=1;
    	for (register int i=head[u];i;i=edge[i].next){
    		int v=edge[i].to;
    		if (v!=father){
    			dist[v]=dist[u]+edge[i].num;
    			dfs1(v,u);
    			siz[u]+=siz[v];
    			if (son[u]==-1||siz[v]>siz[son[u]]) son[u]=v;
    		}
    	}
    }
    int top[300005];
    void dfs2(int u,int tp){
    	top[u]=tp;
    	if (son[u]==-1) return ;
    	dfs2(son[u],tp);
    	for (register int i=head[u];i;i=edge[i].next){
    		int v=edge[i].to;
    		if (v!=fa[u]&&v!=son[u]){
    			dfs2(v,v);
    		}
    	}
    }
    int LCA(int u,int v){
    	while (top[u]!=top[v]){
    		if (dep[top[u]]>dep[top[v]]) u=fa[top[u]];
    		else v=fa[top[v]];
    	}
    	if (dep[u]<dep[v]) return u;
    	return v;
    }//树链剖分求LCA 
    int tmp,maxn,l,r,mid,ans,cnt[300005],e,lca[300005],dis[300005],dif[300005];
    void prepare(int u,int father){
    	dif[u]=cnt[u];
    	for (register int i=head[u];i;i=edge[i].next){
    		int v=edge[i].to;
    		if (v!=father){
    			prepare(v,u);
    			dif[u]+=dif[v];
    		}
    	}
    }
    bool dfs(int u,int father,int k,int ed){
    	for (register int i=head[u];i;i=edge[i].next){
    		int v=edge[i].to;
    		if (v!=father){
    			if (dif[v]==ed&&edge[i].num>=k) return 1;
    			if (dfs(v,u,k,ed)) return 1;
    		}
    	}
    	return 0;
    }
    bool check(int k){
    	memset (dif,0,sizeof (dif));
    	memset (cnt,0,sizeof (cnt));
    	e=0;
    	if (maxn<=k) return 1;
    	for (register int i=1;i<=m;++i){
    		if (dis[i]>k){
    			++e;
    			++cnt[from[i]];++cnt[to[i]];cnt[lca[i]]-=2;
    		}
    	}
    	prepare(1,0);
    	return dfs(1,0,maxn-k,e);
    }//树上差分代码 
    int main(){
    	memset (son,-1,sizeof (son));
    	read(n);read(m);
    	for (register int i=1;i<n;++i){
    		read(x);read(y);read(z);
    		add(x,y,z);add(y,x,z);
    		tmp=max(tmp,z);
    	}
    	dfs1(1,0);dfs2(1,1);
    	for (register int i=1;i<=m;++i){
    		read(from[i]);read(to[i]);
    		lca[i]=LCA(from[i],to[i]);
    		dis[i]=dist[from[i]]+dist[to[i]]-dist[lca[i]]*2;
    		r=max(r,dis[i]);
    	}
    	maxn=r;l=r-tmp;
    	while (l<=r){
    		mid=l+r>>1;
    		if (check(mid)) ans=mid,r=mid-1;
    		else l=mid+1;
    	}
    	write(ans);EL; 	
    	return 0;
    }
    template<class T1>void read(T1 &r_e_a_d){
        T1 k=0;
        char ch=getchar();
        int flag=1;
        while(!isNum(ch)){
            if(ch=='-'){
                flag=-1;
            }
            ch=getchar();
        }
        while(isNum(ch)){
            k=((k<<1)+(k<<3)+ch-'0');
            ch=getchar();
        }
        r_e_a_d=flag*k;
    }
    template<class T1>void write(T1 w_r_i_t_e){
        if(w_r_i_t_e<0){
            putchar('-');
            write(-w_r_i_t_e);
        }else{
            if(w_r_i_t_e<10){
                putchar(w_r_i_t_e+'0');
            }else{
                write(w_r_i_t_e/10);
                putchar((w_r_i_t_e%10)+'0');
            }
        }
    }

转载于:https://www.cnblogs.com/DFTMR/p/10756238.html