Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //DOPAJUL CONTINUA
- //ALGORITMUL LUI PRIM WOO
- #include<stdio.h>
- #include<climits>
- #include<algorithm>
- #include<vector>
- #define MAXV 200000
- #define MAXE 400000
- #define INF INT_MAX
- struct HipHipHooray
- {
- int vertex,cost;
- };
- struct Edge
- {
- int src,dst,cost;
- };
- //FUNCTII MULTE DE HEAPURI
- int left_son(int nod);
- int right_son(int nod);
- int father(int nod);
- void add(int vertex,int cost);
- void rmv(int nod);
- void sift(int nod);
- void percolate(int nod);
- void swap_nodes(int nod1,int nod2);
- void init();
- FILE*fin,*fout;
- HipHipHooray heap[MAXV+1];
- int pos[MAXV+1];
- int e[MAXV+1];
- bool in_heap[MAXV+1];
- Edge edges[MAXE+1];
- int sol[MAXE+1];
- std::vector<int> neighbors[MAXV+1];
- int N=0;
- int E,V;
- int main()
- {
- fin=fopen("apm.in","r");
- fout=fopen("apm.out","w");
- fscanf(fin,"%d%d",&V,&E);
- for(int i=1;i<=E;i++)
- {
- fscanf(fin,"%d%d%d",&edges[i].src,&edges[i].dst,&edges[i].cost);
- neighbors[edges[i].src].push_back(i);
- neighbors[edges[i].dst].push_back(i);
- }
- init();
- int nrsol=0;
- int totalCost=0;
- while(N>0)
- {
- int v=heap[1].vertex;
- rmv(1);
- if(e[v]!=0)
- {
- sol[++nrsol]=e[v];
- totalCost+=edges[e[v]].cost;
- }
- for(unsigned int i=0;i<neighbors[v].size();i++)
- {
- int muchie=neighbors[v][i];
- int vec=(v==edges[muchie].src)?edges[muchie].dst:edges[muchie].src;
- if(in_heap[vec] && heap[pos[vec]].cost>edges[muchie].cost)
- {
- heap[pos[vec]].cost=edges[muchie].cost;
- e[vec]=muchie;
- percolate(pos[vec]);
- }
- }
- }
- fprintf(fout,"%d\n%d\n",totalCost,nrsol);
- for(int i=1;i<=nrsol;i++)
- {
- fprintf(fout,"%d %d\n",edges[sol[i]].src,edges[sol[i]].dst);
- }
- fclose(fin);
- fclose(fout);
- return 0;
- }
- int left_son(int nod)
- {
- return 2*nod;
- }
- int right_son(int nod)
- {
- return 2*nod+1;
- }
- int father(int nod)
- {
- return nod/2;
- }
- void add(int vertex,int cost)
- {
- heap[++N].vertex=vertex;
- heap[N].cost=cost;
- pos[vertex]=N;
- in_heap[vertex]=1;
- percolate(N);
- }
- void rmv(int nod)
- {
- in_heap[heap[nod].vertex]=0;
- swap_nodes(nod,N);
- N--;
- if(nod>1 && heap[nod].cost<heap[father(nod)].cost)
- {
- percolate(nod);
- }
- else
- {
- sift(nod);
- }
- }
- void sift(int nod)
- {
- int son;
- do
- {
- son=0;
- if(right_son(nod)<=N)
- {
- if(heap[left_son(nod)].cost<heap[right_son(nod)].cost)
- {
- son=left_son(nod);
- }
- else
- {
- son=right_son(nod);
- }
- }
- else if(left_son(nod)<=N)
- {
- son=right_son(nod);
- }
- if(heap[nod].cost<heap[son].cost)
- {
- son=0;
- }
- if(son)
- {
- swap_nodes(nod,son);
- nod=son;
- }
- }while(son);
- }
- void percolate(int nod)
- {
- while(nod>1 && heap[nod].cost<heap[father(nod)].cost)
- {
- swap_nodes(nod,father(nod));
- nod=father(nod);
- }
- }
- void swap_nodes(int nod1,int nod2)
- {
- std::swap(heap[nod1].vertex,heap[nod2].vertex);
- std::swap(heap[nod1].cost,heap[nod2].cost);
- std::swap(pos[heap[nod1].vertex],pos[heap[nod2].vertex]);
- }
- void init()
- {
- for(int i=1;i<=V;i++)
- {
- add(i,INF);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement