10807  Prim
Moderator: Board moderators

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Your solution is not working for the following input: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...
Code: Select all
4
6
1 2 10
1 3 10
1 4 10
2 3 10
2 4 10
3 4 10
0
Code: Select all
60

 Experienced poster
 Posts: 136
 Joined: Fri Apr 15, 2005 3:47 pm
 Location: Singapore
 Contact:
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?
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!
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???
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;
}
Re: 10807  Prim, Prim.
Try this case..
Last edited by helloneo on Sun Jun 07, 2009 8:34 am, edited 2 times in total.
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.
Help me please.
Node=4
Edge=5
BUT you gave 4 edge here.
I still get WA.
Help me please.
Re: 10807  Prim, Prim.
Sorry for the wrong test case..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.
Help me please.
I edited it..
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???
Thnx for your reply.
I cant understand why for this case output 22.
My output No way!.
Would you please explain me why output 22???
Thnx for your reply.
Re: 10807  Prim, Prim.
Sorry for confusing.. I made a test case for 10806
Here is a correct test case
Output
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
Code: Select all
34
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.
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.
Re: 10807  Prim, Prim.
The 1st MST is (12), (23), (24) and the cost is 1 + 1+ 10 = 12
The 2nd MST is (12), (24), (34) and the cost is 1 + 20 + 1 = 22
So, the total cost is 34
The 2nd MST is (12), (24), (34) and the cost is 1 + 20 + 1 = 22
So, the total cost is 34
Re: 10807  Prim, Prim.
Thnx again for consulting.
But Why not this solution???
The 1st MST is (12), (23), (34) and the cost is 1 + 1+ 1 = 3
The 2nd MST is (12), (24), (34) and the cost is 1 + 10 + 100 = 111
Why not??
Please tell me.
Is here anything I miss out?
But Why not this solution???
The 1st MST is (12), (23), (34) and the cost is 1 + 1+ 1 = 3
The 2nd MST is (12), (24), (34) and the cost is 1 + 10 + 100 = 111
Why not??
Please tell me.
Is here anything I miss out?
Re: 10807  Prim, Prim.
The problem statements say
So, it should be 34the total cost of this operation needs to be as small as possible