Codeforces Round #661 (Div. 3) E1. Weights Division (easy version) 题解 dfs树的遍历+贪心+优先队列

绝地灬酷狼 2022-11-25 11:43 117阅读 0赞

[原题链接：E1. Weights Division (easy version)][E1. Weights Division _easy version]

#### 题目描述 ####

![题目描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]

#### 输入输出描述 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 1]

#### 题意 ####

就是说给出n个点的树，给出最小值s，每次操作可以把某条边的权值减少一半（下取整），问最少操作多少次使得从根结点遍历所有叶结点的权值和小于s

#### 思路 ####

这道题主要是贪心的思想，计算遍历所有叶结点后，每条边被用了几次，记为x，用x乘权值w，就是该边的最终权值。操作一次可以将该边的最终权值减少一半，那么我们每次就取操作一次减少的权值最大的边进行操作，用while循环直到总权值和sum<s即可。  
那么每条边被用了几次怎么计算呢，我们可以用该边的终点能到达的叶结点个数来计算该边被用的次数。

#### 代码解析 ####

#include<iostream>
    #include<queue>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const int N = 2e5+5;
    
    int e[N],ne[N],w[N],h[N],idx,n;	//链式前向星存树
    ll s,sum,ans;	//sum是总权值和，ans是答案操作次数，
    
    struct node	//结构体，记录某边的权值是多少，被用了多少次
    { 
    	ll val,leaf;
    	friend bool operator < (node a,node b)	//重载运算符，使优先队列是按照操作一次减少的权值排列
    	{ 
    		return (a.val-a.val/2)*a.leaf < (b.val-b.val/2)*b.leaf;
    	}
    };
    
    priority_queue<node> q;	//优先队列q
    
    void add(int a,int b,int c)	//链式前向星加边函数
    { 
    	e[idx] = b;
    	ne[idx] = h[a];
    	w[idx] = c;
    	h[a] = idx++;
    }
    
    ll dfs(int pre,int cur)		//dfs找每条边能到达多少个叶结点，cur是当前结点，pre是上一个结点，防止反向递归
    { 
    	ll leaf = 0;	//初始置0
    	for(int i = h[cur];~i;i = ne[i])	//循环当前点出发的所有边
    	{ 
    		int to = e[i];
    		if(to != pre)	//当终点不是上一个点时
    		{ 
    			ll temp = dfs(cur,to);	//递归下一层
    			q.push({ w[i],temp});	//将当前点入队
    			sum += temp * w[i];	//计算权值总和
    			leaf += temp;		//计算当前结点的叶结点总和 
    		}
    	}
    	if(leaf)	//如果leaf不等于0
    		return leaf;	//返回leaf
    	else
    		return 1;	//如果等于0，说明到叶结点了，返回1；
    }
    
    int main()
    { 
    	int t,a,b,c;
    	cin >> t;
    	while(t--)
    	{ 
    		cin >> n >> s;
    		while(q.size())	//清空队列
    			q.pop();
    		memset(h,-1,sizeof h);	//链式前向星的初始化
    		ans = sum = idx = 0;	
    		for(int i = 1;i < n;i++)
    		{ 
    			cin >> a >> b >> c;
    			add(a,b,c);	//树是无向图
    			add(b,a,c);
    		}
    		dfs(0,1);	//从0，1开始搜索
    		while(sum > s)	//当sum<s的时候
    		{ 
    			ll val = q.top().val;
    			ll leaf = q.top().leaf;
    			q.pop();	//队首出队
    			sum -= (val-val/2)*leaf;	//sum总和减去权值一半乘以计算次数，权值结果下取整，就等于减去的数上取整
    			val /= 2;	//权值减一半，下取整
    			q.push({ val,leaf});	//将操作后的权值和次数入队
    			ans++;		//操作次数+1
    		}
    		cout << ans << endl;	
    	}
    
    	return 0;
    }

[E1. Weights Division _easy version]: https://codeforces.com/contest/1399/problem/E1
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70]: /images/20221124/350a7bd6b86f40b8be90ba40ea4490d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NzM1ODUx_size_16_color_FFFFFF_t_70 1]: /images/20221124/cb0131f6c4744936b338ff41f0edcd80.png