您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

【luogu CF1119F】【luogu P7600】Niyaz and Small Degrees / 封闭道路

Niyaz and Small Degrees / 封闭道路

题目链接:luogu CF1119F / luogu P7600

题目大意

给一棵树,边有边权,是砍掉的费用。
对于每个 x,询问最少要花费费用砍边,使得每个点都不与超过 x 个点相连。

思路

首先看到题目容易想到要 DP。
那我们就想想 n 2 l o g n n^2logn n2logn 的 DP,我们枚举 x x x,然后搞 O ( n l o g n ) O(nlogn) O(nlogn) DP。

那就是设 f i , 0 / 1 f_{i,0/1} fi,0/1 i i i 与父亲连边删或不删时以 i i i 为根的子树的点都满足度数不大于 x x x 的最小费用。
在度数没有限制的时候,那对于 u u u 的儿子 v v v,之间边权为 w w w,有 f u , 0 = f u , 1 = min ⁡ { f v , 0 , f v , 1 + w } f_{u,0}=f_{u,1}=\min\{f_{v,0},f_{v,1}+w\} fu,0=fu,1=min{fv,0,fv,1+w}

那如果有了度数限制,那我们就要想,你选左边就是割,右边就是不割。
那对于 f u , 0 f_{u,0} fu,0,它就一定要选 d u u − x du_u-x duux 个左边的。( d u u du_u duu u u u 的度数)
那对于 f u , 1 f_{u,1} fu,1,它就一定要选 d u u − x − 1 du_u-x-1 duux1 个左边的。
那容易想到,如果本来就是左边优,那我们肯定选左边。那我们可以提前选,然后记得要选的个数要减。
那如果是右边优,那我们就看如果硬要选左边会亏多少( f v , 1 + w − f v , 0 f_{v,1}+w-f_{v,0} fv,1+wfv,0),那我们肯定优先硬改亏的最少的,那我们可以用堆来找到前 d u u − x du_u-x duux 个的总费用。
那就可以了。

那我们考虑怎么优化。
不难想到,如果 x ≥ d u u x\geq du_u xduu,那 u u u 这个点割不割都无所谓,那我们可以把这个点删掉。
但不能把别的点入度修改,而且别的点就相当于有一个费用是 w w w w w w 是它与这个点的边的边权)放进了堆里面。而且这个是一只存在的,不像我们上面算法的堆,那些要清空,而这些要留下。

那我们就要弄一个可删堆,可以用两个普通的堆来维护。
(大概就是你要删你就不直接删而是放进删除堆,每次你要取之前如果你的普通堆和删除堆堆顶相同就把它弹出不要,即我们不立刻删掉,而是阻碍到再删)
(具体是看看代码)

那我们接着继续想,那每次枚举 x x x,DP 的规模就不是 n l o g n nlogn nlogn,而是 m l o g m mlogm mlogm m m m 时度数超过 x x x 的点数)
那这个所有 m m m 加起来的规模其实是 O ( n ) O(n) O(n) 级别的,因为你想,入度和是 2 n 2n 2n,那一个点入度是 x x x 就会贡献 x x x 次,那总共就最多贡献 2 n 2n 2n 次,所以 m m m 就是 O ( n ) O(n) O(n) 级别。
复杂度也就变成了 O ( n l o g n ) O(nlogn) O(nlogn)

具体的实现可以看看代码。

代码

由于两道题是一模一样的,而且 APIO 由于那个交互代码会有点乱,这里就只在 CF 的那个上面写注释。

然后记得两个的点编号一个是 1 ∼ n 1\sim n 1n,一个是 0 ∼ n − 1 0\sim n- 1 0n1

Niyaz and Small Degrees

#include<queue>
#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long

using namespace std;

int n, x, y, z, du[250001], xx[250001];
int nd, kil, in[250001];
vector <pair<int, int> > e[250001];
ll sum, f[250001][2], re;
vector <ll> ans, tmp, del;

struct cd_heap {//可删堆
	priority_queue <int> q1, q2;
	ll sum;
	void insert(int x) {q1.push(x); sum += x;}
	void delete_(int x) {q2.push(x); sum -= x;}
	void ck() {while (!q1.empty() && !q2.empty() && q1.top() == q2.top()) q1.pop(), q2.pop();}
	int top() {ck(); return q1.top();}
	void pop() {ck(); sum -= q1.top(); q1.pop();}
	int size() {return q1.size() - q2.size();}
}h[250001];

void add(int x, int y, int z) {
	e[x].push_back(make_pair(y, z));
	du[x]++;
}

bool cmp0(pair <int, int> x, pair <int, int> y) {
	return du[x.first] > du[y.first];
	//优化,枚举相连的点时按相连点入度从大到小枚举
	//如果枚举到已被删去,那后面的点都被删了,就可以直接退出了
}

bool cmp(int x, int y) {
	return du[x] < du[y];
}

void kill(int x) {//删点
	for (int i = 0; i < e[x].size(); i++){
		int y = e[x][i].first, z = e[x][i].second;
		if (du[y] <= nd) break;
		h[y].insert(z);//相连的边要留着,相当于单独费用是 z 的(因为不砍不会有花费,z-0=z)
	}
}

void dfs(int now, int father) {
	in[now] = nd;
	int num = du[now] - nd;//看要砍多少边
	while (h[now].size() > num)//维护堆只有这么多个边(下同)
		h[now].pop();
	
	for (int i = 0; i < e[now].size(); i++) {//dfs 递归 DP
		int to = e[now][i].first;
		if (du[to] <= nd) break;
		if (to == father) continue;
		dfs(to, now);
	}
	
	tmp.clear(); del.clear();//记得清空
	for (int i = 0; i < e[now].size(); i++) {
		int to = e[now][i].first, dis = e[now][i].second;
		if (du[to] <= nd) break;
		if (to == father) continue;
		ll x = f[to][1] + dis - f[to][0];
		if (x <= 0) {//明显是不割优
			re += f[to][1] + dis;
			num--;//这个直接处理乘割了,那要割的数量就少了
		}
		else {
			re += f[to][0];
			del.push_back(x);//把这里加进堆的记录下来,因为只有这一次可以用,那我们搞完要删掉它们
			h[now].insert(x);
		}
	}
	
	//tmp 是存丢出去的,由于也是只是这一次用,那我们到时还要放回去,丢出去只是为了统计费用
	while (h[now].size() && h[now].size() > num)
		tmp.push_back(h[now].top()), h[now].pop();
	f[now][0] = h[now].sum;//不删父亲的
	while (h[now].size() && h[now].size() > num - 1)//删父亲就代表要多删一条
		tmp.push_back(h[now].top()), h[now].pop();
	f[now][1] = h[now].sum;//删父亲的
	
	for (int i = 0; i < tmp.size(); i++)//记得把要还原的还原,把要删的删了
		h[now].insert(tmp[i]);
	for (int i = 0; i < del.size(); i++)
		h[now].delete_(del[i]);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		scanf("%d %d %d", &x, &y, &z);
		add(x, y, z);
		add(y, x, z);
		sum += z;
	}
	
	ans.push_back(sum);
	for (int i = 1; i <= n; i++) {
		sort(e[i].begin(), e[i].end(), cmp0);
		xx[i] = i;
	}
	
	sort(xx + 1, xx + n + 1, cmp);
	
	kil = 1;
	while (++nd < n) {
		while (kil <= n && nd == du[xx[kil]]) kill(xx[kil]), kil++;//有新的可以直接删掉的点
		if (kil > n) {//所有点都被删掉了,后面答案都是 0
			ans.push_back(0);
			continue;
		}
		
		re = 0;
		for (int i = kil; i <= n; i++) {//DP,记得要枚举每个树
			if (in[xx[i]] == nd) continue;
			dfs(xx[i], 0);	
			re += f[xx[i]][0];
		}
		
		ans.push_back(re);
	}
	
	for (int i = 0; i < ans.size(); i++)
		printf("%lld ", ans[i]);
	
	return 0;
}

封闭道路

#include<queue>
#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long

using namespace std;

int n, x, y, z, du[250001], xx[250001];
int nd, kil, in[250001];
vector <pair<int, int> > e[250001];
ll sum, f[250001][2], re;
vector <ll> ans, tmp, del;

struct cd_heap {
	priority_queue <int> q1, q2;
	ll sum;
	void insert(int x) {q1.push(x); sum += x;}
	void delete_(int x) {q2.push(x); sum -= x;}
	void ck() {while (!q1.empty() && !q2.empty() && q1.top() == q2.top()) q1.pop(), q2.pop();}
	int top() {ck(); return q1.top();}
	void pop() {ck(); sum -= q1.top(); q1.pop();}
	int size() {return q1.size() - q2.size();}
}h[250001];

void add(int x, int y, int z) {
	e[x].push_back(make_pair(y, z));
	du[x]++;
}

bool cmp0(pair <int, int> x, pair <int, int> y) {
	return du[x.first] > du[y.first];
}

bool cmp(int x, int y) {
	return du[x] < du[y];
}

void kill(int x) {
	for (int i = 0; i < e[x].size(); i++){
		int y = e[x][i].first, z = e[x][i].second;
		if (du[y] <= nd) break;
		h[y].insert(z);
	}
}

void dfs(int now, int father) {
	in[now] = nd;
	int num = du[now] - nd;
	while (h[now].size() > num)
		h[now].pop();
	
	for (int i = 0; i < e[now].size(); i++) {
		int to = e[now][i].first;
		if (du[to] <= nd) break;
		if (to == father) continue;
		dfs(to, now);
	}
	
	tmp.clear(); del.clear();
	for (int i = 0; i < e[now].size(); i++) {
		int to = e[now][i].first, dis = e[now][i].second;
		if (du[to] <= nd) break;
		if (to == father) continue;
		ll x = f[to][1] + dis - f[to][0];
		if (x <= 0) {
			re += f[to][1] + dis;
			num--;
		}
		else {
			re += f[to][0];
			del.push_back(x);
			h[now].insert(x);
		}
	}
	
	while (h[now].size() && h[now].size() > num)
		tmp.push_back(h[now].top()), h[now].pop();
	f[now][0] = h[now].sum;
	while (h[now].size() && h[now].size() > num - 1)
		tmp.push_back(h[now].top()), h[now].pop();
	f[now][1] = h[now].sum;
	
	for (int i = 0; i < tmp.size(); i++)
		h[now].insert(tmp[i]);
	for (int i = 0; i < del.size(); i++)
		h[now].delete_(del[i]);
}

std::vector<long long> minimum_closure_costs(int N, std::vector<int> U,
                                             std::vector<int> V,
                                             std::vector<int> W) {
    n = N;
	for (int i = 1; i < n; i++) {
		x = U[i - 1] + 1;
		y = V[i - 1] + 1;
		z = W[i - 1];
		add(x, y, z);
		add(y, x, z);
		sum += z;
	}
	
	ans.push_back(sum);
	for (int i = 1; i <= n; i++) {
		sort(e[i].begin(), e[i].end(), cmp0);
		xx[i] = i;
	}
	
	sort(xx + 1, xx + n + 1, cmp);
	
	kil = 1;
	while (++nd < n) {
		while (kil <= n && nd == du[xx[kil]]) kill(xx[kil]), kil++;
		if (kil > n) {
			ans.push_back(0);
			continue;
		}
		
		re = 0;
		for (int i = kil; i <= n; i++) {
			if (in[xx[i]] == nd) continue;
			dfs(xx[i], 0);	
			re += f[xx[i]][0];
		}
		
		ans.push_back(re);
	}
	
	return ans;
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进