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 }