codeforces 1283F. DIY Garland(树+优先队列)
2024-09-06 14:24:53
题目连接:https://codeforces.com/contest/1283/problem/F
题意:一根电线连接着两个点,这两个点分别代表着两个灯,灯有自己的编号i,其亮度是2 ^ i,每根电线的两个灯分别为主灯和副灯,电源从主灯来,电流向副灯。最开始有一个源点灯,所有的电源从此处流入,对于每根电线,定义其重要性为 :切断这根电线后不能通电的所有灯的亮度之和。首先题目按电线的重要性给出n-1条电线的主灯编号,让你从大到小输出每条电线所连接的两个灯的序号(无前后差别)
题解:首先,题目的所描述的结构是一棵树,因为题目是按电线重要性给出的节点主灯,那么第一个节点必定是源点,因为重要性最大。其次因为树的叶子节点度必为1,而且叶子节点必定不是主灯,那么我们可以在输入之后统计叶子节点,同时统计一下输入节点的度。叶子节点的编号用优先队列存储,因为亮度最小最先和重要性低的电线匹配。因为输入的时候电线是按重要性从大到小输入的,那么我们就可以把优先队列中的节点一个一个地与其父亲节点(主灯)匹配,匹配过后,让当前这个主灯的度-1,如果这个此时度变为1,那么加入到优先队列之中,因为他现在成了“叶子节点”,如此过程直到把n-1条边都找到,break即可
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int maxn = 2e5+;
int ind[maxn];
vector<pair<int,int> > ans;
int main(){
int n;
cin>>n;
priority_queue<int, vector<int>,greater<int> > q;
vector<int> mainLamp;
int gird = -;
for(int i = ;i<n-;i++){
int lamp;
cin>>lamp;
if(gird == -) gird = lamp;//记录源点
ind[lamp]++;//记录度
mainLamp.push_back(lamp);
}
for(int i = ;i<=n;i++){
if(ind[i] == ){//寻找未出现的叶子节点
q.push(i);
}
}
while(!q.empty() ){
int cur = q.top();
q.pop();
int curMainLamp = mainLamp[mainLamp.size()-];
mainLamp.pop_back();//匹配一个主灯,就弹出一个
ans.push_back({curMainLamp,cur});//加入一条边
if(ans.size() == n - ) break;
ind[curMainLamp]--;
if(ind[curMainLamp] == ){
q.push(curMainLamp);//如果度为0,那么变成了叶子节点,加入队列中
}
}
cout<<gird<<endl;
for(int i = ans.size() -;i>= ;i--){
cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
return ;
}
最新文章
- .Net(c#)模拟Http请求之HttpWebRequest封装
- JS判断字符串长度的5个方法
- sphinx应用
- 集合框架之——迭代器并发修改异常ConcurrentModificationException
- (8) 深入理解Java Class文件格式(七)
- MySQL数据库从GBK转换到UTF-8最简单解决方案(也适用于其它编码转换)
- json在php中的使用之如何转换json为数组
- [Effective JavaScript 笔记]第25条:使用bind方法提取具有确定接收者的方法
- alloc和初始化的定义
- 最近纠结致死的一个java报错java.net.SocketException: Connection reset 终于得到解决
- Flink从入门到放弃(入门篇1)-Flink是什么
- 如何去maven仓库下载jar包
- HTML学习笔记Day3
- dedecms 模版里格式化时间标签
- linux 2.6.32文件系统的dentry父子关系
- 微信小程序 - 分包加载(预下载)
- Windows Phone 的这几年
- 北风网VIP6级学习视频地址
- 关于Centos的yum安装LAMP
- 20145312 《Java程序设计》第三周学习总结