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 »

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

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

Post 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

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

Post by jan_holmes »

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 »

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 »

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.

Post 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;
}

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

Re: 10807 - Prim, Prim.

Post by helloneo »

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.

Post 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.

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

Re: 10807 - Prim, Prim.

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

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

Re: 10807 - Prim, Prim.

Post 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.

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

Re: 10807 - Prim, Prim.

Post 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

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

Re: 10807 - Prim, Prim.

Post 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.

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

Re: 10807 - Prim, Prim.

Post 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

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

Re: 10807 - Prim, Prim.

Post 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?

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

Re: 10807 - Prim, Prim.

Post by helloneo »

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)”