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.

Post by sady » 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;
}

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

Re: 10807 - Prim, Prim.

Post by brianfry713 » Fri Jan 17, 2014 12:01 am

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!

Post Reply

Return to “Volume 108 (10800-10899)”