codeforces 1283F. DIY Garland(树+优先队列)

题目连接:https://codeforces.com/contest/1283/problem/F

题意:一根电线连接着两个点,这两个点分别代表着两个灯,灯有自己的编号i,其亮度是2 ^ i,每根电线的两个灯分别为主灯和副灯,电源从主灯来,电流向副灯。最开始有一个源点灯,所有的电源从此处流入,对于每根电线,定义其重要性为 :切断这根电线后不能通电的所有灯的亮度之和。首先题目按电线的重要性给出n-1条电线的主灯编号,让你从大到小输出每条电线所连接的两个灯的序号(无前后差别)

题解:首先,题目的所描述的结构是一棵树,因为题目是按电线重要性给出的节点主灯,那么第一个节点必定是源点,因为重要性最大。其次因为树的叶子节点度必为1,而且叶子节点必定不是主灯,那么我们可以在输入之后统计叶子节点,同时统计一下输入节点的度。叶子节点的编号用优先队列存储,因为亮度最小最先和重要性低的电线匹配。因为输入的时候电线是按重要性从大到小输入的,那么我们就可以把优先队列中的节点一个一个地与其父亲节点(主灯)匹配,匹配过后,让当前这个主灯的度-1,如果这个此时度变为1,那么加入到优先队列之中,因为他现在成了“叶子节点”,如此过程直到把n-1条边都找到,break即可

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue> 
 7 using namespace std;
 8 const int maxn = 2e5+5;
 9 int ind[maxn];
10 vector<pair<int,int> > ans;
11 int main(){
12     int n;
13     cin>>n;
14     priority_queue<int, vector<int>,greater<int> > q;
15     vector<int> mainLamp;
16     int gird = -1;
17     for(int i = 0;i<n-1;i++){
18         int lamp;
19         cin>>lamp;
20         if(gird == -1) gird = lamp;//记录源点
21         ind[lamp]++;//记录度
22         mainLamp.push_back(lamp);
23     }
24     for(int i = 1;i<=n;i++){
25         if(ind[i] == 0){//寻找未出现的叶子节点
26             q.push(i); 
27         }
28     }
29     while(!q.empty() ){    
30         int cur = q.top();
31         q.pop();
32         int curMainLamp = mainLamp[mainLamp.size()-1];
33         mainLamp.pop_back();//匹配一个主灯,就弹出一个
34         ans.push_back({curMainLamp,cur});//加入一条边
35         if(ans.size() == n -1 ) break;
36         ind[curMainLamp]--;
37         if(ind[curMainLamp] == 0){
38             q.push(curMainLamp);//如果度为0,那么变成了叶子节点,加入队列中
39         }
40     }
41     cout<<gird<<endl;
42     for(int i = ans.size() -1;i>=0 ;i--){
43         cout<<ans[i].first<<" "<<ans[i].second<<endl;
44     }
45     return 0;
46 }
上一篇:Garland


下一篇:【广搜】魔板