Pagini recente » Cod sursa (job #100517) | Cod sursa (job #299516) | Cod sursa (job #2878651) | Cod sursa (job #1939133) | Cod sursa (job #1006335)
#include<fstream>
#include<vector>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
const int Nmax = 200005;
const int Mmax = 400005;
int N,M;
int insideAPM[Nmax];
struct vertex{
int dest,cost;
};
vector<vertex> G[Nmax];
struct apm_link{
int a,b;
};
vector<apm_link> APM;
int ans;
struct heap_item{
int val,node,origin;
} H[Nmax+Mmax]; int L;
void swap(int a,int b){
heap_item X=H[a];
H[a]=H[b];
H[b]=X;
}
void upheap(int i){
if(i/2>0 && H[i/2].val>H[i].val){
swap(i/2,i);
upheap(i/2);
}
}
void downheap(int i){
if(2*i+1<=L && H[2*i+1].val<H[i].val && H[2*i+1].val<=H[2*i].val){
swap(i,2*i+1);
downheap(2*i+1);
}
else if(2*i<=L && H[2*i].val<H[i].val){
swap(2*i,i);
downheap(2*i);
}
}
heap_item First(){
heap_item X=H[1];
swap(1,L);
--L;
downheap(1);
return X;
}
void Push(heap_item X){
H[++L]=X;
upheap(L);
}
int main(){
in>>N>>M;
for(int i=1;i<=M;i++){
int x,y,c;
vertex u;
in>>x>>y>>c;
u.cost=c;
u.dest=y;
G[x].push_back(u);
u.dest=x;
G[y].push_back(u);
}
for(vector<vertex>::iterator it=G[1].begin();it!=G[1].end();++it){
heap_item start;
start.val=it->cost;
start.node=it->dest;
start.origin=1;
Push(start);
}
insideAPM[1]=1;
while(L>0){
heap_item p=First();
if(!insideAPM[p.node]){
insideAPM[p.node]=1;
ans+=p.val;
apm_link u;
u.a=p.origin;
u.b=p.node;
APM.push_back(u);
for(vector<vertex>::iterator it=G[p.node].begin();it!=G[p.node].end();++it){
if(!insideAPM[it->dest]){
heap_item pp;
pp.val=it->cost;
pp.node=it->dest;
pp.origin=p.node;
Push(pp);
}
}
}
}
out<<ans<<'\n';
out<<APM.size()<<'\n';
for(vector<apm_link>::iterator it=APM.begin();it!=APM.end();++it){
out<<it->a<<' '<<it->b<<'\n';
}
return 0;
}