## 10807 - Prim

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sady
New poster
Posts: 17
Joined: Sat Dec 07, 2013 8:00 am

### Re: 10807 - Prim, Prim.

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;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10807 - Prim, Prim.

Input:

Code: Select all

``````9
24
3 1 757
4 8 594
2 4 918
9 4 365
1 5 700
9 3 736
7 8 758
9 5 891
9 4 374
6 9 473
3 2 473
8 5 553
1 5 928
1 8 628
7 1 363
4 6 811
4 9 391
6 9 376
7 2 95
3 4 624
4 2 611
4 2 515
6 9 660
3 4 497
9
9
1 7 822
1 7 630
2 5 393
3 2 719
5 4 973
4 9 543
1 6 167
2 8 601
1 7 426
6
7
2 5 548
4 2 486
4 3 203
6 1 253
4 3 907
2 5 221
3 2 388
3
22
1 3 757
3 2 830
3 1 160
3 1 321
1 2 50
3 1 13
3 2 516
3 2 272
2 1 505
1 3 944
3 1 189
2 1 544
2 1 2
1 2 518
1 3 836
1 2 220
1 3 287
3 1 715
2 3 562
2 1 535
1 2 79
3 1 535
7
17
4 2 421
4 6 969
5 6 419
2 4 76
1 7 642
2 3 115
2 7 648
3 2 483
4 2 17
3 7 19
4 1 727
7 5 955
3 2 128
5 1 17
5 4 677
7 6 83
7 3 280
2
19
1 2 324
2 1 404
1 2 533
1 2 922
1 2 76
2 1 421
1 2 377
2 1 180
2 1 180
1 2 976
2 1 82
2 1 843
2 1 493
1 2 10
2 1 734
2 1 295
2 1 913
2 1 126
1 2 89
9
24
6 8 631
4 8 136
8 6 618
8 3 527
8 1 129
5 7 975
4 3 785
3 7 533
9 6 430
5 2 60
6 9 196
1 7 753
6 4 300
4 9 554
1 7 314
4 1 838
4 2 796
5 4 495
6 3 524
4 5 997
6 8 859
1 8 302
9 4 53
9 5 653
10
6
4 1 91
10 8 293
6 2 970
9 2 179
6 10 509
3 9 899
10
21
4 9 455
4 8 508
4 10 851
8 6 825
1 4 744
10 9 671
1 10 897
2 5 566
3 8 744
2 3 286
5 8 755
10 2 109
2 7 920
8 5 903
1 5 668
3 4 415
1 7 132
10 8 29
6 3 125
10 6 743
8 7 645
7
20
2 7 168
7 6 0
6 4 251
4 3 718
5 4 130
5 1 596
5 7 348
7 3 545
5 6 743
4 3 524
1 7 349
7 3 71
2 6 514
6 1 80
7 6 147
3 2 371
1 4 108
4 7 851
7 3 65
1 6 961
3
13
1 2 614
1 2 734
3 1 457
3 2 181
2 3 337
2 3 733
2 1 545
1 3 81
2 3 193
2 1 370
3 2 714
3 1 147
1 3 588
2
15
1 2 380
2 1 461
1 2 804
1 2 675
1 2 548
1 2 386
2 1 683
1 2 98
1 2 941
2 1 394
1 2 878
1 2 603
1 2 371
1 2 854
2 1 714
7
15
6 1 750
1 3 143
2 6 58
3 5 691
6 4 447
7 2 485
4 2 826
4 5 847
6 7 121
7 1 466
1 2 961
3 6 279
5 1 660
3 4 106
1 4 281
10
10
9 1 552
4 3 88
8 7 744
7 9 839
6 2 76
3 2 62
5 1 0
8 9 479
6 8 515
6 10 757
4
6
2 1 652
3 1 732
4 1 587
2 4 701
4 2 737
2 1 242
5
17
5 4 610
1 4 286
1 4 254
1 4 946
1 4 924
2 1 173
4 3 634
4 1 934
5 2 589
5 3 720
3 5 47
1 5 669
5 2 774
4 3 87
2 3 402
3 2 29
4 5 446
3
23
1 2 144
2 3 854
3 2 206
2 1 215
3 2 929
2 1 278
3 1 418
1 3 253
1 2 377
2 3 146
3 1 457
2 3 63
3 1 279
1 3 469
3 2 981
1 2 778
1 3 68
2 3 264
1 3 100
2 3 557
3 1 788
2 1 570
1 3 451
7
22
5 6 108
2 4 886
5 3 954
5 7 908
3 7 8
2 6 565
7 5 43
2 4 633
4 6 113
7 5 718
4 2 826
4 5 46
3 7 928
4 6 471
7 3 536
6 2 876
7 4 78
7 3 423
2 6 393
7 6 145
1 3 245
3 7 863
8
16
4 6 655
8 3 67
4 5 768
7 4 696
6 3 972
7 1 345
2 8 854
4 2 789
7 2 652
3 1 676
1 3 235
3 1 361
7 3 566
3 2 382
5 4 219
5 4 893
8
8
1 6 552
8 7 203
2 7 879
8 4 633
4 2 909
4 6 93
7 5 545
3 6 208
0
``````
AC output:

Code: Select all

``````8132
No way!
No way!
225
3200
86
6066
No way!
9271
2088
602
469
4487
No way!
No way!
1724
375
No way!
7561
No way!
``````
Check input and AC output for thousands of problems on uDebug!