E1. Weights Division (easy version)
题意
给出一个n个点n-1条边以1号点为根的树每条边有权重(距离)wi
现在定义一种操作：wi=wi/2
现在要求在最小操作次数的前提下满足：
$∑_{v∈leaves}w(root,v)=sum≤S $
S已经给出其中w(root,v)表示从根到某个叶子结点的距离
题解
很显然这需要算边的贡献
每条边要被算入总长度sum几次=这条路通到几个子节点 用一个dfs来搜索每个点下面有几个叶子结点
然后这条路对总长度sum的贡献为 val(i,j)*sz[j] 表示(i,j)这条路被使用过sz[j]次,sz[j]就是以j为根的子树中有几个叶子结点,而且对于一条路它肯定是由某个结点连它一个父节点 所有的结点它的父节点唯一，那么可以用这个点来表示指定的路比如val(i,j)表示父节点i -> 子节点 j的路 可以直接用val[j]表示
然后就是怎么贪心做wi=wi/2的操作问题 首先想到根据 val[i]*sz[i] 排序 大的优先 /2 但是这里需要注意
val[i]*sz[i] 是由val[i]和sz[i]共同决定的 而每次操作只能对val[i]=val[i]/2
所以根据 val[i]*sz[i]排序贪心不合理 而根据这条路val[i]被减半后带来的收益来排序
也就是sz[i]×val[i]-(val[i]/2)×sz[i] 来排序
具体的
将{sz[i]×val[i]-(val[i]/2ll)×sz[i],i}作为一个pair放入降序的优先队列
同时记录一个sum=∑sz[i]*val[i]
每次取出堆头 sum-( sz[i]×val[i]-(val[i]/2ll)×sz[i])
然后更新对这条边下一次操作的收益
即将val[i]/=2后 再次压入{sz[i]×val[i]-(val[i]/2ll)×sz[i],i}到优先队列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=1e5+5;
const double PI=acos(-1);
vector<pair<int,ll> >mp[Max];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,less<pair<ll,ll> > >q;
ll sz[Max],val[Max];
void dfs_size(int now,int per){
if(mp[now].size()==1)sz[now]=1;
else sz[now]=0;
for(auto i:mp[now]){
if(i.first==per)continue;
val[i.first]=i.second;
dfs_size(i.first,now);
sz[now]+=sz[i.first];
}
}
int main() {
Turnoff;
int t;cin>>t;
while(t--){
ll n,s;cin>>n>>s;
for(int i=1;i<n;i++){
int u,v,w;cin>>u>>v>>w;
mp[u].push_back({v,w});
mp[v].push_back({u,w});
}
dfs_size(1,0);
while(!q.empty())q.pop();
ll sum=0;
for(int i=1;i<=n;i++){
q.push({sz[i]*val[i]-(val[i]/2ll)*sz[i],i});
sum+=sz[i]*val[i];
}
int cnt=0;
while(sum>s){
pair<ll,ll>temp=q.top();q.pop();
sum-=temp.first;
val[temp.second]/=2ll;
temp.first=sz[temp.second]*val[temp.second]-(val[temp.second]/2ll)*sz[temp.second];
q.push(temp);
cnt++;
}
cout<<cnt<<endl;
for(int i=1;i<=n;i++)mp[i].clear(),val[i]=0,sz[i]=0;
}
}
|
E2. Weights Division (hard version)
题意
和easy version类似 只不过每条边多了个属性
对他做一次w/=2操作会产生对应的cost(1<=cost<=2)
现在问使得$∑_{v∈leaves}w(root,v)=sum≤S$
最小的花费
题解
将两种花费的边分别独立处理
只对cost=1的边进行操作,
将所有cost=1的边按照easy的贪心方法逐个操作
直到所有cost=1的边 的$∑wi=0$ 每次操作时将当前的$∑wi$单独存入v1
只对cost=2的边进行操作
将所有cost=2的边按照easy的贪心方法逐个操作
直到所有cost=2的边 的$∑wi=0$ 每次操作时将当前的$∑wi$单独存入v2
然后可以用二分或者双指针 对于所有v1[i] 寻找到一个最大的v2[j]且小于等于s-v1[i]
则最小花费更新为ans=min(ans,i+2*j)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
using namespace std;
typedef long long ll;
const ll Max=1e5+5;
const double PI=acos(-1);
vector<pair<int,pair<ll,int> > >mp[Max];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,less<pair<ll,ll> > >q[3];
ll sz[Max],val[Max],n,s;
int cost[Max];
/*
*/
void dfs_size(int now,int per){
if(mp[now].size()==1)sz[now]=1;
else sz[now]=0;
for(auto i:mp[now]){
if(i.first==per)continue;
val[i.first]=i.second.first;
cost[i.first]=i.second.second;
dfs_size(i.first,now);
sz[now]+=sz[i.first];
}
}
vector<ll> get(int c){
vector<ll>res;
ll sum=0;
for(int i=1;i<=n;i++){
//cout<<val[i]<<" "<<sz[i]<<" "<<i<<endl;
if(cost[i]!=c)continue;
q[c].push({sz[i]*val[i]-(val[i]/2ll)*sz[i],i});
sum+=sz[i]*val[i];
}
res.push_back(sum);
while(sum>0&&!q[c].empty()){
pair<ll,ll>temp=q[c].top();q[c].pop();
sum-=temp.first;
res.push_back(sum);
val[temp.second]/=2ll;
temp.first=sz[temp.second]*val[temp.second]-(val[temp.second]/2ll)*sz[temp.second];
q[c].push(temp);
}
return res;
}
void init(){
while(!q[1].empty())q[1].pop();
while(!q[2].empty())q[2].pop();
}
int main() {
//Turnoff;
int t;cin>>t;
while(t--){
cin>>n>>s;
init();
for(int i=1;i<n;i++){
int u,v,w,c;cin>>u>>v>>w>>c;
mp[u].push_back({v,{w,c}});
mp[v].push_back({u,{w,c}});
}
dfs_size(1,0);
//cout<<"ok"<<endl;
vector<ll>v1=get(1),v2=get(2);
//cout<<"ok"<<endl;
ll ans=1e18,pos=v2.size()-1,len=v1.size();
for(int i=0;i<len;i++){
//cout<<"in"<<endl;
while(pos>0&&v1[i]+v2[pos-1]<=s)pos--;
if(v1[i]+v2[pos]<=s)ans=min(ans,i+2*pos);
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)mp[i].clear(),val[i]=0,sz[i]=0,cost[i]=0;
}
}
|