首页 > 其他分享 >P2680 [NOIP2015 提高组] 运输计划

P2680 [NOIP2015 提高组] 运输计划

时间:2024-04-07 13:57:38浏览次数:24  
标签:std 运输 NOIP2015 int top 路径 P2680 son dep

P2680 [NOIP2015 提高组] 运输计划

二分+树剖

开始题目理解错了,这里的最短时间指的是所有路径的最大值。所以题目要求的就是让所有路径的最大值最小,显然可以二分

二分最大值 \(x\),那么假如一条路径长度为 \(d\) 并且 \(d>x\),显然需要修改,即一定要删去路径上的一条边 \((u,v)\),满足 \(d-w(u,v)\le x\),即 \(w(u,v)\ge d-x\)。开始的时候想的做法是,把每条路径满足这个条件的边标记+1,最后看是否有这样的边满足标记等于需要修改的路径数,可我们并没有这样一个数据结构能够快速找到满足这种条件的边。

考虑另一个角度,可以发现我们要修改的边一定是所有需要修改的路径的交集,所以我们完全可以找到这个交集,再判断交集内的边是否有满足 \(w\ge\max(d)-x\)。这个做法只需要把需要修改的路径上的边+1,树剖即可。这里的角度是把修改的边集找出来,最后再判断边集中是否有边满足条件

先二分,再树剖标记,这样的复杂度为 \(O((m\log n+n)\log V)\),可以通过。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back

typedef long long i64;
const i64 iinf = 0x3f3f3f3f, linf = 0x3f3f3f3f3f3f3f3f;
const int N = 3e5 + 10;
int n, m, cnt;
int dis[N], h[N];
std::array<int, 3> G[N];
bool cmp(std::array<int, 3> a, std::array<int, 3> b) {
	return a[2] > b[2];
}
struct node {
	int to, nxt, w;
} e[N << 1];
void add(int u, int v, int w) {
	e[++cnt].to = v, e[cnt].nxt = h[u], e[cnt].w = w, h[u] = cnt;
}
int num;
int sz[N], dep[N], id[N], son[N], fa[N], top[N], val[N];
void dfs1(int u, int f) {
	sz[u] = 1;
	dep[u] = dep[f] + 1;
	fa[u] = f;
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].w;
		if(v == f) continue;
		dis[v] = dis[u] + w;
		dfs1(v, u);
		val[v] = w;
		sz[u] += sz[v];
		if(sz[v] > sz[son[u]]) son[u] = v;
	} 
}	
void dfs2(int u, int topf) {
	top[u] = topf;
	id[u] = ++num;
	if(!son[u]) return;
	dfs2(son[u], topf);
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa[u] || v == son[u]) continue;
		dfs2(v, v);
	}
}
int lca(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
		u = fa[top[u]]; 
	}
	if(dep[u] > dep[v]) std::swap(u, v);
	return u; 
}
struct seg {
	int v, lzy;
} t[N << 2];
void pushup(int u) {t[u].v = t[u << 1].v + t[u << 1 | 1].v;}
void pd(int u, int l, int r) {
	if(!t[u].lzy) return;
	int mid = (l + r) >> 1;
	t[u << 1].v += (mid - l + 1) * t[u].lzy; t[u << 1 | 1].v += (r - mid) * t[u].lzy;
	t[u << 1].lzy += t[u].lzy, t[u << 1 | 1].lzy += t[u].lzy;
	t[u].lzy = 0;
}
void build(int u, int l, int r) {
	t[u].v = t[u].lzy = 0;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r, int x) {
	if(l == r) return t[u].v;
	int mid = (l + r) >> 1; pd(u, l, r);
	if(x <= mid) return query(u << 1, l, mid, x);
	return query(u << 1 | 1, mid + 1, r, x);
} 
void update(int u, int l, int r, int L, int R, int x) {
	if(L <= l && r <= R) {
		t[u].v += (r - l + 1) * x;
		t[u].lzy += x;
		return;
	}
	int mid = (l + r) >> 1; pd(u, l, r);
	if(L <= mid) update(u << 1, l, mid, L, R, x);
	if(R > mid) update(u << 1 | 1, mid + 1, r, L, R, x);
	pushup(u);
}
void mdf(int u, int v) {
	while(top[u] != top[v]) {
		if(dep[top[u]] < dep[top[v]]) std::swap(u, v);
		update(1, 1, n, id[top[u]], id[u], 1);
		u = fa[top[u]];
	}
	if(dep[u] > dep[v]) std::swap(u, v);
	update(1, 1, n, id[u] + 1, id[v], 1);
} 
bool check(int x) {
	build(1, 1, n);
	int cnt = 0, mx = 0, nd = 0;
	for(int i = 1; i <= m; i++) {
		if(G[i][2] <= x) break;
		mdf(G[i][0], G[i][1]); cnt++;  
	}
	if(!cnt) return 1;
	for(int i = 2; i <= n; i++) {
		if(query(1, 1, n, id[i]) == cnt) mx = std::max(mx, val[i]);
	} 
	return mx >= G[1][2] - x;
}
void Solve() {
	std::cin >> n >> m;

	for(int i = 1; i < n; i++) {
		int u, v, w;
		std::cin >> u >> v >> w;
		add(u, v, w), add(v, u, w); 
	}

	dfs1(1, 0), dfs2(1, 1);
	for(int i = 1; i <= m; i++) {
		std::cin >> G[i][0] >> G[i][1];
		int rt = lca(G[i][0], G[i][1]);
		G[i][2] = dis[G[i][0]] + dis[G[i][1]] - 2 * dis[rt];
	}
	std::sort(G + 1, G + m + 1, cmp);
	int l = 0, r = 300000000, ans = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(check(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	std::cout << ans << "\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}

标签:std,运输,NOIP2015,int,top,路径,P2680,son,dep
From: https://www.cnblogs.com/FireRaku/p/18118889

相关文章

  • P2678 [NOIP2015 提高组] 跳石头
    思路:运用两次数组比较,按照序号和前后相差距离的大小比较排序。代码:首次尝试30分#include<algorithm>#include<iostream>#include<cstring>#include<queue>#include<cmath>usingnamespacestd;intm,n;longlongl;inta[50010];structnode{ intid; intch......
  • P1967 [NOIP2013 提高组] 货车运输 题解
    P1967[NOIP2013提高组]货车运输原题地址思路:由于题目要求的是使两点之间的最小边权最大,所以可以构造最大生成树(最大生成树一定是最大瓶颈生成树,而瓶颈生成树上两点之间的路径,在原图中的所有路径中,最小边权仍然最大,即满足题目要求,详见https://oi-wiki.org/graph/mst/#性质),......
  • 【IEEE会议征稿通知】第九届信息科学、计算机技术与交通运输国际学术会议(ISCTT 2024)
    【IEEE会议】第九届信息科学、计算机技术与交通运输国际学术会议(ISCTT2024)20249th InternationalConferenceonInformationScience,ComputerTechnologyandTransportation   第九届信息科学、计算机技术与交通运输国际学术会议(ISCTT2024)将于2024年6月28-30......
  • 航空运输岗位技能证/危险品运输训练合格证
    《民用航空运输销售代理岗位技能培训合格证》(国际货运或国内货运)是中国航空运输协会(CATA)颁发的岗位合格证书,俗称“上岗证”“民航上岗证”。中国民用航空运输销售代理岗位技能培训合格证分类:1.按照货运与客运分类为:货运上岗证、客运上岗证;2.按照国际与国内分类为:国......
  • 最大化运输问题求解——Python实现
    运输问题(TransportationProblem)是运筹学中的经典问题,通常涉及将资源从供应点转移到需求点,以最小化运输成本或满足需求。这个问题在各种实际场景中都有广泛的应用,包括但不限于以下几个方面:供应链管理:在供应链中,最小化运输问题可用于确定最有效的货物运输方式,以满足各个节点之间的......
  • P2615 [NOIP2015 提高组] 神奇的幻方
    P2615[NOIP2015提高组]神奇的幻方[NOIP2015提高组]神奇的幻方题目背景NOIp2015提高组Day1T1题目描述幻方是一种很神奇的\(N\timesN\)矩阵:它由数字\(1,2,3,\cdots\cdots,N\timesN\)构成,且每行、每列及两条对角线上的数字之和都相同。当\(N\)为奇数时,我们......
  • 货车运输
    借这一道题目来介绍一下最小瓶颈路和Kruscal重构树首先本来这道题目我其实是没看出来是最大生成树的(因为不知道上面两个东西),然后我想的是二分,当然也可以做,但是复杂度多一个\(log\)对上面两个东西的介绍见OI-wiki下面是一些解释最小瓶颈路的性质的第一句话说“根据最小生成树定......
  • 【TWVRP】遗传算法求解带时间窗的车辆路径规划(目标函数:运输成本、惩罚成本)【含Matlab
    ......
  • 货车运输(LCA+最大生成树)
    货车运输这题会有重边,又因为求的是尽可能大的边中的最小值,所以我们可以先用最大生成树维护,如何用最大生成树呢?可以用Kruskal和并查集,顺便处理重边,处理完重边后,可以用倍增LCA求两点之间的最大载重量处理重边时,必须把dis在x,y相同情况下大的排在前,以保证最优,用并查集find判断是否......
  • LightningChart为运输和物流行业创建数据可视化应用
    使用LightningChart为运输和物流行业创建数据可视化应用程序查看运输和物流图表用于构建物流应用程序的LightningChart组件开发人员可以通过轻松集成LightningChart.NET或JavaScript图表预构建组件,为运输和物流行业构建数据可视化应用程序......