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:

Post by jan_holmes » Sun Jun 04, 2006 8:58 pm

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Fri Jun 09, 2006 6:31 pm

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

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

Post by jan_holmes » Sat Jun 17, 2006 8:47 pm

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:

Post by Moha » Thu Aug 03, 2006 12:11 am

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

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Nov 05, 2006 9:41 am

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!

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

Re: 10807 - Prim, Prim.

Post by sreejond » Fri Jun 05, 2009 9:18 pm

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.

Post by helloneo » Sat Jun 06, 2009 5:19 am

Try this case..

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

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

Re: 10807 - Prim, Prim.

Post by sreejond » Sat Jun 06, 2009 6:13 am

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.

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

Re: 10807 - Prim, Prim.

Post by helloneo » Sat Jun 06, 2009 11:19 am

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.. :-)

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

Re: 10807 - Prim, Prim.

Post by sreejond » Sun Jun 07, 2009 6:17 am

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.

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

Re: 10807 - Prim, Prim.

Post by helloneo » Sun Jun 07, 2009 8:37 am

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

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

Re: 10807 - Prim, Prim.

Post by sreejond » Sun Jun 07, 2009 11:58 am

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.

Post by helloneo » Sun Jun 07, 2009 12:33 pm

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

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

Re: 10807 - Prim, Prim.

Post by sreejond » Sun Jun 07, 2009 1:23 pm

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?

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

Re: 10807 - Prim, Prim.

Post by helloneo » Sun Jun 07, 2009 2:36 pm

The problem statements say
the total cost of this operation needs to be as small as possible
So, it should be 34 :-)

Post Reply

Return to “Volume 108 (10800-10899)”