首页 > 其他分享 >P6594 [YsOI2020] 换寝室

P6594 [YsOI2020] 换寝室

时间:2024-04-13 12:11:44浏览次数:24  
标签:rt std 连通 YsOI2020 anc int 寝室 fa P6594

P6594 [YsOI2020] 换寝室

树上差分+树形 dp

题意:给定一棵树,每条边有边权,割掉一些边,使得被割掉的边边权和不超过 kk ,最小化剩余连通块点权极差的最大值。

看到最小化最大值,可以考虑二分

此时二分了 \(x\),那么每个连通块的极差都不能超过 \(x\)。考虑需要判断是否存在一个连通块的划分方式,使得满足条件并且代价不超过 \(k\),即最小化代价

考虑树形 dp。解决的问题是子树中满足条件的最小代价,然后可以加一个状态方便转移,考虑记录当前连通块的信息。设 \(f_{u,i}\) 表示划分完满足条件的 \(u\) 子树,包含 \(u\) 的连通块最小值为 \(a_i\) 的最小代价。转移枚举每个子树 \(v\) 是否与 \(u\) 在同一个连通块内。

\(f_{u,i}=\sum\min(f_{v,i},mn+val(u,v))\)

若最小值相同,那么无需断边;否则不在同一个连通块内,一定需要断边(不然肯定在一个连通块内)。这时候就有一个问题,有时候会出现不合法的情况,比如断边之后无法满足出现这样两个连通块。但是我们发现这种情况是不会更优的,也就是不会对答案产生贡献

考虑初始化,我们需要知道每个点的连通块中能够出现哪些最小值,限制是二分的 \(x\),只需要每个点跑一遍 dfs 即可

复杂度 \(O(n^2)\)。

#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 = 810;
int n, m, k, l = iinf, r, ans;
int dep[N], anc[N][11], sz[N], w[N], a[N];
std::vector<int> e[N];
void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1;
	anc[u][0] = fa;
	for(int i = 1; i <= 10; i++) anc[u][i] = anc[anc[u][i - 1]][i - 1];
	for(auto v : e[u]) {
		if(v == fa) continue;
		dfs(v, u);
	}
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) std::swap(u, v);
	for(int i = 10; i >= 0; i--) if(dep[anc[u][i]] >= dep[v]) u = anc[u][i];
	if(u == v) return u;
	for(int i = 10; i >= 0; i--) if(anc[u][i] != anc[v][i]) u = anc[u][i], v = anc[v][i];
	return anc[u][0];
}
void dfs2(int u, int fa) {
	for(auto v : e[u]) {
		if(v == fa) continue;
		dfs2(v, u);
		w[u] += w[v];
	}
} //lca+树上差分
int now;
int vis[N], f[N][N];
void find(int u, int fa, int rt) {
	vis[u] = 1;
	for(auto v : e[u]) {
		if(v == fa) continue;
		if(a[v] < a[rt] || a[v] - a[rt] > now) continue; 
		find(v, u, rt);
	}
} //包含 rt 的连通块中最小值是否可以是 a[rt]
void dfs3(int u, int fa) {
	int mn;
	for(auto v : e[u]) {
		if(v == fa) continue;
		mn = iinf;
		dfs3(v, u);
		for(int i = 1; i <= n; i++) mn = std::min(mn, f[v][i]);
		for(int i = 1; i <= n; i++) {
			f[u][i] += std::min(f[v][i], mn + w[v]);
		}
	}
}
bool check(int x) {
	now = x;
	for(int u = 1; u <= n; u++) {
		memset(vis, 0, sizeof(vis));
		find(u, 0, u);
		for(int i = 1; i <= n; i++) {
			if(vis[i]) f[i][u] = 0;
			else f[i][u] = iinf;
		}
	}
	dfs3(1, 0);
	for(int i = 1; i <= n; i++) {
		if(f[1][i] <= k) return true;
	}
	return false;
}
void Solve() {
	std::cin >> n >> m >> k;

	for(int i = 1; i <= n; i++) {
		std::cin >> a[i];
		l = std::min(l, a[i]), r = std::max(r, a[i]);
	}

	for(int i = 1; i < n; i++) {
		int u, v;
		std::cin >> u >> v;
		e[u].pb(v), e[v].pb(u);
	}
	dfs(1, 0);
	for(int i = 1; i <= m; i++) {
		int x, y;
		std::cin >> x >> y;
		int rt = lca(x, y);
		w[x]++, w[y]++, w[rt] -= 2;
	}
	dfs2(1, 0);
	r = r - l, l = 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;
}

标签:rt,std,连通,YsOI2020,anc,int,寝室,fa,P6594
From: https://www.cnblogs.com/FireRaku/p/18132670

相关文章

  • L1-095 分寝室
    暴力枚举。#include<bits/stdc++.h>usingnamespacestd;constintinf=0x3f3f3f3f;intres1,res2;intmain(){ inta,b,c;//女生男生寝室数 cin>>a>>b>>c; intminsub=inf; for(inti=2;i<a;i++){//i表示女生几人间 if(a%i==0&&c-a......
  • L1-7 分寝室 [java]
    分数20学校新建了宿舍楼,共有 n 间寝室。等待分配的学生中,有女生 n0​ 位、男生 n1​ 位。所有待分配的学生都必须分到一间寝室。所有的寝室都要分出去,最后不能有寝室留空。现请你写程序完成寝室的自动分配。分配规则如下:男女生不能混住;不允许单人住一间寝室;对每种性......
  • 7-4 分寝室(c语言)
    目录目录目录题目第一次错误代码第二次错误代码最终结果题目学校新建了宿舍楼,共有n间寝室。等待分配的学生中,有女生n0位、男生n1位。所有待分配的学生都必须分到一间寝室。所有的寝室都要分出去,最后不能有寝室留空。现请你写程序完成寝室的自动分配。分配规则如下:男女......
  • hdu:搬寝室
    ProblemDescription搬寝室是很累的,xhd深有体会.时间追述2006年7月9号,那天xhd迫于无奈要从27号楼搬到3号楼,因为10号要封楼了.看着寝室里的n件物品,xhd开始发呆,因为n是一个小于2000的整数,实在是太多了,于是xhd决定随便搬2k件过去就行了.但还是会很累,因为2k也不小是一个不大......
  • HDU1421 搬寝室
    题目:搬寝室 典型的DP,状态方程:dp[k][i]=min(dp[k-1][i-2]+(a[i]-a[i-1])^2,dp[k][i-1]);        dp[k][i]表示k对物品在前i个物品的最小值#include<iostream>#include<stdio.h>#include<algorithm>#defineN2005usingnamespacestd;intdp[N/2][N];inta[N......
  • 23-5-18--练习--分寝室
    L1-7分寝室分数 20学校新建了宿舍楼,共有 n 间寝室。等待分配的学生中,有女生 n0​ 位、男生 n1​ 位。所有待分配的学生都必须分到一间寝室。所有的寝室都要分出去,最后不能有寝室留空。现请你写程序完成寝室的自动分配。分配规则如下:男女生不能混住;不允许单人......
  • P6591 [YsOI2020]植树
    树上操作太薄弱了,根本想不出来。思路:首先自定义根做一遍dfs,求出sz数组,sz[i]表示i的子树大小。在做第二遍dfs,对每一个点进行尝试,看能否为根。当x点为根转移到y点为......
  • Java基于springboot大学生宿舍寝室考勤人脸识别管理系统
    简介Java基于springboot开发的大学生寝室管理系统宿舍管理系统。学生可以查找寝室和室友信息,可以申请换寝室,申请维修,寝室长提交考勤信息(宿管确认学生考勤信息),补签,查看寝室......
  • 实现实验室和寝室两台电脑文件实时同步
    考虑到白天去实验室工作,晚上又要回寝室,文件传输会很麻烦,于是寻求能够方便进行文件远程同步的方案。1.使用工具内网穿透:zerotier(全平台均可)文件同步(备份)工具:FreeFileSync(Win......
  • 实现实验室和寝室两台电脑文件实时同步
    考虑到白天去实验室工作,晚上又要回寝室,文件传输会很麻烦,于是寻求能够方便进行文件远程同步的方案。1.使用工具内网穿透:zerotier(全平台均可)文件同步(备份)工具:FreeFileSyn......