![:D](./images/smilies/icon_biggrin.gif)
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..
![:-)](./images/smilies/icon_smile.gif)
![:-)](./images/smilies/icon_smile.gif)
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.
![:(](./images/smilies/icon_frown.gif)
I edited it..
![:-)](./images/smilies/icon_smile.gif)
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???
![:(](./images/smilies/icon_frown.gif)
Thnx for your reply.
Re: 10807 - Prim, Prim.
Sorry for confusing.. I made a test case for 10806 ![:-(](./images/smilies/icon_frown.gif)
Here is a correct test case
Output
![:-(](./images/smilies/icon_frown.gif)
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 (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
The 2nd MST is (1-2), (2-4), (3-4) 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 (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??
Please tell me.
Is here anything I miss out?
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??
Please tell me.
Is here anything I miss out?
Re: 10807 - Prim, Prim.
The problem statements say
![:-)](./images/smilies/icon_smile.gif)
So, it should be 34the total cost of this operation needs to be as small as possible
![:-)](./images/smilies/icon_smile.gif)