Re: 10807 - Prim, Prim.
Posted: Mon Jan 06, 2014 11:58 am
i used kruskal . greedily add edges to A and B simultaneously. getting WA. plz give me some critical input for which my code not working.
Code: Select all
//prim prim
//simultaniously kruskal apply krte hbe aladavabe kruskal apply kora jbe na
//greedily a b r jnno edge select krte hbe
#include<iostream>
#include<cstdio>
#include<list>
#include<map>
using namespace std;
list<pair<int, pair<int,int> > > sort_edge;
map<int , int > parent1;
map<int, int> rank1;
map<int , int > parent2;
map<int, int> rank2;
void kruskal(int vertices, int edges);
void initialize(int vertices);
void Union(int start, int end);
int main()
{
int vertices,m,i, start, end, weight;//n num of vertices, m num of edges
while(scanf("%d", &vertices) && vertices)
{
cin>>m;//edge
sort_edge.clear();
for(i=0;i<m;++i)
{
cin>>start>>end>>weight;
sort_edge.push_back(make_pair(weight, make_pair(start,end)));
}
sort_edge.sort();
kruskal(vertices,m);
}
return 0;
}
int find_set(int node, map<int , int > parent)
{
while(parent[node]!=node)
{
node=parent[node];
}
return node;
}
void initialize(int vertices)
{
parent1.clear();
rank1.clear();
parent2.clear();
rank2.clear();
int i;
for(i=1;i<=vertices;++i)
{
parent2[i]=parent1[i]=i;
rank2[i]=rank1[i]=0;
}
return;
}
void Union(int start, int end,map<int , int > parent,map<int , int > rank)
{
if(rank[start] > rank[end] ) parent[end]=start;//start is parent as it has more child
else
{
parent[start]=end;
if(rank[start]==rank[end]) ++rank[end];//parent rank barabo cz
}
}
void kruskal(int vertices,int edges)
{
if(edges< (vertices-1)*2)
{
cout<<"No way!\n";
return;
}
list<pair<int, pair<int, int> > > ::iterator it;
int countA=0,countB=0, sumA=0,sumB=0, weight, start, end, pA1, pB2,pB1, pA2 ;
initialize(vertices);
while( (countA!=vertices-1 || countB!=vertices-1) && !sort_edge.empty() )
{
it=sort_edge.begin();
weight= it->first;
start=it->second.first;
end=it->second.second;
sort_edge.pop_front();
pA1=find_set(start,parent1 ), pA2=find_set(end, parent1);
pB1=find_set(start,parent2 ),pB2=find_set(end, parent2);
if(pA1!=pA2)
{
Union(pA1, pA2,parent1, rank1);
++countA;
sumA+=weight;
it=sort_edge.begin();
if(it!=sort_edge.end())
{
weight= it->first;
start=it->second.first;
end=it->second.second;
pB1=find_set(start,parent2 ),pB2=find_set(end, parent2);
if(pB1!=pB2)
{
Union(pB1, pB2,parent2, rank2);//iff 2ta set union krbo
++countB;
sumB+=weight;
sort_edge.pop_front();
}
}
}
//B set r jnno min line select krte hbe
else if(pB1!=pB2)
{
Union(pB1, pB2,parent2, rank2);
++countB;
sumB+=weight;
}
}
//printf("edgeA=%d sumA=%d\nedgeB=%d sumB=%d\n", countA, sumA, countB, sumB);
if(countA!=vertices-1 || countB!=vertices-1)cout<<"No way!\n";
else cout<<sumA+sumB<<endl;
return;
}