## 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

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
I've read the topic,but didn't found something that could help me because in this problem,I'm using another implementation... Please at least,give me some critical I/O... Thx...

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
jan_holmes wrote:I've read the topic,but didn't found something that could help me because in this problem,I'm using another implementation... Please at least,give me some critical I/O... Thx...
Your solution is not working for the following input:

Code: Select all

``````4
6
1 2 10
1 3 10
1 4 10
2 3 10
2 4 10
3 4 10
0``````
The correct output is:

Code: Select all

``60``

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
Thx Martin... I will try to fix my program...

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:
Can anybody post some testcases? I got WA. I use backtracking method on edges.
I did a very nasty bug! now i got it.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
can any one plz give some test case? i am getting WA

my algo is:

sort edges in ascending order. then see if the edge can be taken into tree A or B. if cant be taken in any proceed with not taking. if it is possible to take in A/B try it by taking. if it can be taken in both then by bktk take them in both and proceed.

is it wrong algo?
Self judging is the best judging!

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 10807 - Prim, Prim.

Help needed.
I got WA in this problem.
I try lot to find it.
Seems to be a very easy problem cant figure it out.
I do Kruskal here.
Can anybody please check my code???

Code: Select all

``````#include<iostream.h>
#include<stdlib.h>
#include<string.h>

#define MAXN 50

int P[MAXN], Rank[MAXN], Check[MAXN];

int Node, edg, Cost, f;

struct edge
{
int u, v;
int cost;
};

edge Edge[MAXN*MAXN];
edge Path[MAXN];

int com(const void *xy, const void *xz)
{
edge *x = (edge*)xy;
edge *y = (edge*)xz;
return (x->cost - y->cost);
}

void In()
{ // initializing parent and rank for each node
int i;
for(i = 1; i<= Node; i++)
{
P[i] = i;
Rank[i] = 1;
}
}

int Find(int n)
{ // find the parent of a node
if(P[n] != n)
P[n] = Find(P[n]);
return P[n];
}

void Link(int x, int y)
{ // joining the nodes
if(Rank[x] > Rank[y])
{
P[y] = x;
}
else
{
P[x] = y;
if(Rank[x] == Rank[y])
Rank[y]++;
}
}

void Kruscal()
{
int x, y,total = 0;
Cost = f = 0;
for(int i = 0; i<edg; i++)
{
x = Find(Edge[i].u);
y = Find(Edge[i].v);
if(x != y && Check[i]==0)
{ // if not cycle

Check[i] = 1;
Path[total++] = Edge[i];
Link(x,y); // join those node
Cost += Edge[i].cost;
if(total == Node - 1)
{
f=1;
break;
}
}
}
}

void Cal()
{
long C;
qsort(Edge,edg,sizeof(edge),com); // sorting the edges respect to cost
Kruscal();
C=Cost;
if(f)
{
In();
Kruscal();
C+=Cost;
}
if(f)
cout<<C<<endl;
else
cout<<"No way!\n";

}

int main()
{
int i;
while(cin>>Node)
{ // reading number of node and edge
if(!Node)
break;
cin>>edg;
In();
memset(Check,0,sizeof(Check));
for(i = 0; i<edg; i++)  // reading each edate with cost
cin>>Edge[i].u>>Edge[i].v>>Edge[i].cost;
Cal();
}
return 0;
}``````

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10807 - Prim, Prim.

Try this case..

Last edited by helloneo on Sun Jun 07, 2009 8:34 am, edited 2 times in total.

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 10807 - Prim, Prim.

Thanx heeloneo for your case but i think in your test case there is some problem.
Node=4
Edge=5
BUT you gave 4 edge here.
I still get WA.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10807 - Prim, Prim.

sreejond wrote:Thanx heeloneo for your case but i think in your test case there is some problem.
Node=4
Edge=5
BUT you gave 4 edge here.
I still get WA.
Sorry for the wrong test case..
I edited it..

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 10807 - Prim, Prim.

Hi helloneo,
I cant understand why for this case output 22.
My output No way!.
Would you please explain me why output 22???

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10807 - Prim, Prim.

Sorry for confusing.. I made a test case for 10806

Here is a correct test case

Code: Select all

``````4
7
1 2 1
1 2 1
2 3 1
2 4 10
2 4 20
3 4 1
3 4 100
0``````
Output

Code: Select all

``34``

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 10807 - Prim, Prim.

Sorry to disturb again.
You say output is 34.
My code give 114.
But I cant get why output is 34.
I draw it but cant get it.
Would you please explain me?
Thnx for your help.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 10807 - Prim, Prim.

The 1st MST is (1-2), (2-3), (2-4) and the cost is 1 + 1+ 10 = 12
The 2nd MST is (1-2), (2-4), (3-4) and the cost is 1 + 20 + 1 = 22

So, the total cost is 34

sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

### Re: 10807 - Prim, Prim.

Thnx again for consulting.
But Why not this solution???
The 1st MST is (1-2), (2-3), (3-4) and the cost is 1 + 1+ 1 = 3
The 2nd MST is (1-2), (2-4), (3-4) and the cost is 1 + 10 + 100 = 111
Why not??