Page 2 of 3

Posted: Sun Jun 04, 2006 8:58 pm
by jan_holmes
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... :D

Posted: Fri Jun 09, 2006 6:31 pm
by Martin Macko
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... :D
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

Posted: Sat Jun 17, 2006 8:47 pm
by jan_holmes
Thx Martin... I will try to fix my program...

Posted: Thu Aug 03, 2006 12:11 am
by Moha
Can anybody post some testcases? I got WA. I use backtracking method on edges.
I did a very nasty bug! now i got it. :D

Posted: Sun Nov 05, 2006 9:41 am
by shanto86
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?

Re: 10807 - Prim, Prim.

Posted: Fri Jun 05, 2009 9:18 pm
by sreejond
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;
}

Re: 10807 - Prim, Prim.

Posted: Sat Jun 06, 2009 5:19 am
by helloneo
Try this case..

:-)

Re: 10807 - Prim, Prim.

Posted: Sat Jun 06, 2009 6:13 am
by sreejond
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.

Re: 10807 - Prim, Prim.

Posted: Sat Jun 06, 2009 11:19 am
by helloneo
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.
Sorry for the wrong test case.. :(
I edited it.. :-)

Re: 10807 - Prim, Prim.

Posted: Sun Jun 07, 2009 6:17 am
by sreejond
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.

Re: 10807 - Prim, Prim.

Posted: Sun Jun 07, 2009 8:37 am
by helloneo
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

Re: 10807 - Prim, Prim.

Posted: Sun Jun 07, 2009 11:58 am
by sreejond
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.

Re: 10807 - Prim, Prim.

Posted: Sun Jun 07, 2009 12:33 pm
by helloneo
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

Re: 10807 - Prim, Prim.

Posted: Sun Jun 07, 2009 1:23 pm
by sreejond
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?

Re: 10807 - Prim, Prim.

Posted: Sun Jun 07, 2009 2:36 pm
by helloneo
The problem statements say
the total cost of this operation needs to be as small as possible
So, it should be 34 :-)