C++-hihoCode-1105/1109-[STL][堆][prime]

 1 #include <set>
 2 #include <map>
 3 #include <cmath>
 4 #include <queue>
 5 #include <vector>
 6 #include <cstdio>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <iostream>
10 #include <algorithm>
11 using namespace std;
12 const int MAXN=100010;
13 priority_queue<int>q;
14 int m,a;string s;
15 int main(){
16     for(cin>>m;m--;){
17         cin>>s;
18         if(s=="A")cin>>a,q.push(a);
19         else {
20             cout<<q.top()<<endl;
21             q.pop();
22         }
23     }
24     return 0;
25 }

 1 #include <set>
 2 #include <map>
 3 #include <cmath>
 4 #include <queue>
 5 #include <vector>
 6 #include <cstdio>
 7 #include <cstdlib>
 8 #include <cstring>
 9 #include <iostream>
10 #include <algorithm>
11 using namespace std;
12 const int MAXN=1e5+10;
13 priority_queue<pair<int,int> >q;
14 vector<pair<int,int> >E[MAXN];
15 int n,m,u,v,w,ans,vis[MAXN];
16 pair<int,int>e;
17 void update(int u){
18     vis[u]=true;
19     for(int i=0;i<E[u].size();i++)
20         if(!vis[E[u][i].second])q.push(E[u][i]);
21 }
22 int main(){
23     for(cin>>n>>m;m--;){
24         cin>>u>>v>>w;
25         E[u].push_back(make_pair(-w,v));
26         E[v].push_back(make_pair(-w,u));
27     }
28     update(1);//以下为prime最小生成树（小根堆优化）算法
29     for(int i=1;i<n;i++)
30         while(!q.empty()){
31             e=q.top(),q.pop(),v=e.second;
32             if(vis[v])continue;
33             ans+=-e.first,update(v);
34             break;
35         }
36     cout<<ans<<endl;
37     return 0;
38 }