首页 > 其他分享 >难存的情缘&货车运输

难存的情缘&货车运输

时间:2024-05-22 10:32:03浏览次数:18  
标签:难存 int tr 货车运输 son 情缘 line now id

事先说明,参考的oceans_of_stars,顺便%一下(有事他背锅

一个求最大,一个求最小,没啥好说的,拿难存的情缘举例说明边权如何转点权


一天机房的夜晚,无数人在MC里奋斗着。。。
大家都知道矿产对于MC来说是多么的重要,但由于矿越挖越少,勇士们不得不跑到更远的地方挖矿,但这样路途上就会花费相当大的时间,导致挖矿效率低下。
cjj提议修一条铁路,大家一致同意。
大家都被CH分配了一些任务:
zjmfrank2012负责绘制出一个矿道地图,这个地图包括家(当然这也是一个矿,毕竟不把家掏空我们是不会走的),和无数个矿,所以大家应该可以想出这是一个无向无环图,也就是一棵树。
Digital_T和cstdio负责铺铁路。。所以这里没他们什么事,两位可以劳作去了。
这个时候song526210932和RMB突然发现有的矿道会刷怪,并且怪的数量会发生变化。作为采矿主力,他们想知道从一个矿到另一个矿的路上哪一段会最困难。。。(困难值用zjm的死亡次数表示)。

输入格式
输入文件的第一行有一个整数N,代表矿的数量。矿的编号是1到N。

接下来N-1行每行有三个整数a,b,c,代表第i号矿和第j号矿之间有一条路,在初始时这条路的困难值为c。

接下来有若干行,每行是“CHANGE i ti”或者“QUERY a b”,前者代表把第i条路(路按所给顺序从1到M编号)的困难值修改为ti,后者代表查询a到b所经过的道路中的最大困难值。

输入数据以一行“DONE”结束。

输出格式
对每个“QUERY”操作,输出一行一个正整数,即最大困难值。

样例
样例输入
3
1 2 1
2 3 2
QUERY 1 2
CHANGE 1 3
QUERY 1 2
DONE
样例输出
1
3
数据范围与提示
对于60%的数据,1<=N<=50

对于100%的数据,1<=N<=10000,1<=c<=1000000,1<=操作次数<=100000

最主要的问题是,如何把边权转点权,以及如何去将修改边转化为修改点
有一个方法就是将边权赋给儿子(边两端中深度较大的那个点)
image
image

对应代码
void dfs1(int now){
	son[now]=-1;
	siz[now]=1;
	for(int i=head[now];i;i=edge[i].from){
		int to=edge[i].to;
		if(dep[to]) continue;
		a[to]=edge[i].w;//这里
		dep[to]=dep[now]+1;
		fa[to]=now;
		dfs1(to);
		siz[now]+=siz[to];
		if(son[now]==-1||siz[to]>siz[son[now]]) son[now]=to;
	}
}

但这样就有两个问题
1.按树剖求路径最大会多算

image
我的本意是想要求4,3与3,3的边的最大值,但实际上还与1,3这条边进行了比较,这会导致误差
所以我们要去掉这个点,实际上也很好像想(不好想)因为这个点的下标一定是两个点跳到同一重链后那个深度浅的点的dfn值,只需要给它+1,就可以解决了
2.对应点,我们存一下每个边的编号,然后修改的的点一定是对应边中深度深的那个点,也可以在一开始的编号中记录一下,都是一样的

第一种
	cnt1++;
	add(from,to,w);
	add(to,from,w);
	line[cnt1].from=from;
	line[cnt1].to=to;
	line[cnt1].w=w;
	//记录边的编号
cin>>from>>to;
int dian=0;		
if(dep[line[from].from]>dep[line[from].to]){
	dian=line[from].from;
}
else dian=line[from].to;
update(1,dfn[dian],to);
//找深度深的点
第二种
void dfs1(int now){
	son[now]=-1;
	siz[now]=1;
	for(int i=head[now];i;i=edge[i].from){
		int to=edge[i].to;
		if(dep[to]) continue;
		a[to]=edge[i].w;
		dian[edge[i].id]=to;//这里
		dep[to]=dep[now]+1;
		fa[to]=now;
		dfs1(to);
		siz[now]+=siz[to];
		if(son[now]==-1||siz[to]>siz[son[now]]) son[now]=to;
	}
}

然后就没了

点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define lson id<<1
#define rson id<<1|1
const int N=1e6+1000;
typedef long long ll;
int n,m,head[N];
int top[N],dfn[N],siz[N],son[N],fa[N];
int a[N],cnt,num,dep[N],b[N];
struct node{
	int l,r,max;
}tr[N<<2];
struct node1{
	int from;
	int to;
	int w;
}edge[N<<2],line[N];
void add(int from,int to,int w){
	cnt++;
	edge[cnt].from=head[from];
	edge[cnt].to=to;
	edge[cnt].w=w;
	head[from]=cnt;
}
void dfs1(int now){
	son[now]=-1;
	siz[now]=1;
	for(int i=head[now];i;i=edge[i].from){
		int to=edge[i].to;
		if(dep[to]) continue;
		a[to]=edge[i].w;
		dep[to]=dep[now]+1;
		fa[to]=now;
		dfs1(to);
		siz[now]+=siz[to];
		if(son[now]==-1||siz[to]>siz[son[now]]) son[now]=to;
	}
}
void dfs2(int now,int tp){
	top[now]=tp;
	num++;
	b[num]=a[now];
	dfn[now]=num;
	if(son[now]==-1) return;
	dfs2(son[now],tp);
	for(int i=head[now];i;i=edge[i].from){
		int to=edge[i].to;
		if(to!=fa[now]&&to!=son[now]) dfs2(to,to);
	}
}
void build(int id,int l,int r){
	tr[id].l=l;
	tr[id].r=r;
	if(l==r){
		tr[id].max=b[l];
		return;
	}
	int mid=(l+r)/2;
	build(lson,l,mid);
	build(rson,mid+1,r);
	tr[id].max=max(tr[lson].max,tr[rson].max);
}
void update(int id,int x,int ad){
	if(tr[id].l==tr[id].r){
		tr[id].max=ad;
		return;
	}
	int mid=(tr[id].l+tr[id].r)/2;
	if(x<=mid) update(lson,x,ad);
	else update(rson,x,ad);
	tr[id].max=max(tr[lson].max,tr[rson].max); 
}
int getmax(int id,int l,int r){
	if(l>tr[id].r||r<tr[id].l) return -0x7fffffff;
	if(l<=tr[id].l&&tr[id].r<=r){
		return tr[id].max;
	}
	return max(getmax(lson,l,r),getmax(rson,l,r));
}
int treemax(int x,int y){
	int maxn=-0x7fffffff;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		maxn=max(maxn,getmax(1,dfn[top[x]],dfn[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	maxn=max(maxn,getmax(1,dfn[x]+1,dfn[y]));
	return maxn;
}
int main(){
	string str;
	int cnt1=0;
	int c,from,to,w;
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>from>>to>>w;
		cnt1++;
		add(from,to,w);
		add(to,from,w);
		line[cnt1].from=from;
		line[cnt1].to=to;
		line[cnt1].w=w;
	}
	dep[1]=1;
	dfs1(1);
	dfs2(1,1);
	build(1,1,n);
	while(cin>>str&&str!="DONE"){
		if(str=="QUERY"){
			cin>>from>>to;
			cout<<treemax(from,to)<<endl;
			
		}
		else {
			cin>>from>>to;
			int dian=0;
			if(dep[line[from].from]>dep[line[from].to]){
				dian=line[from].from;
			}
			else dian=line[from].to;
			update(1,dfn[dian],to);
		}
	}
}

标签:难存,int,tr,货车运输,son,情缘,line,now,id
From: https://www.cnblogs.com/PeppaEvenPigShiGeNiuBDePig/p/18203673

相关文章

  • 难存的情缘
    抽象的题目(咱就是说,这个”难存的情缘“是指要把矿掏空吗)题目分析这个题目还是比较好理解的,我们需要干的有\(2\)个操作,但实际上有\(3\)个1:边权转点权2:单点修改3:链上最大值查询很明显是树刨板子题,操作中需要注意的有三点,如何转边权,最大值点权查多了,修改时的边......
  • P1967 [NOIP2013 提高组] 货车运输 题解
    P1967[NOIP2013提高组]货车运输原题地址思路:由于题目要求的是使两点之间的最小边权最大,所以可以构造最大生成树(最大生成树一定是最大瓶颈生成树,而瓶颈生成树上两点之间的路径,在原图中的所有路径中,最小边权仍然最大,即满足题目要求,详见https://oi-wiki.org/graph/mst/#性质),......
  • 货车运输
    借这一道题目来介绍一下最小瓶颈路和Kruscal重构树首先本来这道题目我其实是没看出来是最大生成树的(因为不知道上面两个东西),然后我想的是二分,当然也可以做,但是复杂度多一个\(log\)对上面两个东西的介绍见OI-wiki下面是一些解释最小瓶颈路的性质的第一句话说“根据最小生成树定......
  • 货车运输(LCA+最大生成树)
    货车运输这题会有重边,又因为求的是尽可能大的边中的最小值,所以我们可以先用最大生成树维护,如何用最大生成树呢?可以用Kruskal和并查集,顺便处理重边,处理完重边后,可以用倍增LCA求两点之间的最大载重量处理重边时,必须把dis在x,y相同情况下大的排在前,以保证最优,用并查集find判断是否......
  • hszxoj 货车运输
    题目链接:hszxoj货车运输题目描述与思路简化题目:求\(x\)到\(y\)两点间路径的边权最小值的最大值与之前的最短路最大的不同是这道题是多源最短路,那么\(spfa\)就废了,\(Floyd\)定会\(TLE\)所以就需要用新的算法。用\(lca\)一定是在树上的,但明显这玩意他既有环又有森......
  • [NOIP 2013提高组]货车运输 题解
    [NOIP2013提高组]货车运输题解前置知识Kruskal重构树(内含讲解)+任意一种LCA题目翻译\(n\)座城市,\(m\)条道路,\(q\)次询问,每次求两个点\(x,y\)之间所有路径的最小值的最大值。题目分析其实学了Kruskal重构树差不多看到这个题目就知道怎么写了。其实就是Kruskal重构树的板子,......
  • P1967 [NOIP2013 提高组] 货车运输 (生成树,LCA)
    P1967[NOIP2013提高组]货车运输https://www.luogu.com.cn/problem/P1967首先有些边是没用的(比较小的边),比如两个点之间的两条(并行的)路,只有较大的会被走到,小的不会被走,因此可以直接去除小的边,即求最大生成树。接着做求任意两点经过的边的最小值就演变成求树上任意两点的最小树......
  • P1967 [NOIP2013 提高组] 货车运输
    P1967[NOIP2013提高组]货车运输因为可能成环,这样可能导致到达点的最小权值不一,所以用最小生成树的方法重新建图然后我是利用倍增的思想建立从i点开始,到上面点的距离ff和最小权值ww因为最小权值不好直接建立,所以不如最后统一建立最后就是寻找最近公共祖先的模板了一组hack......
  • 「NOIP2013」货车运输 题解
    「NOIP2013」货车运输前言这道题算是一个稍有思维难度的MST+LCA题目了。稍微卡了一会(0-88-88-88-100(打表)-100(打表)-100(正解)),开始是打了表过了,后面在DCZ的帮助下正解通过(下面注释提到的一个坑)。题目大意给出一张无向图\(G\),有\(n\)个点和\(m\)个边\((x,y)=z\),找到一......
  • NC16527 [NOIP2013]货车运输
    题目链接题目题目描述A国有n座城市,编号从1到n,城市之间有m条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有q辆货车在运输货物,司机们想知道每辆车在不超过车辆限重的情况下,最多能运多重的货物。输入描述第一行有两个用一个空格隔开的整数n,m,表示A国......