Posted:

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

Page **2** of **3**

Posted: **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...

Posted: **Fri Jun 09, 2006 6:31 pm**

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`

Posted: **Sat Jun 17, 2006 8:47 pm**

Thx Martin... I will try to fix my program...

Posted: **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.

I did a very nasty bug! now i got it.

Posted: **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?

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?

Posted: **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???

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

Posted: **Sat Jun 06, 2009 5:19 am**

Try this case..

Posted: **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.

Node=4

Edge=5

BUT you gave 4 edge here.

I still get WA.

Help me please.

Posted: **Sat Jun 06, 2009 11:19 am**

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

Posted: **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.

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.

Posted: **Sun Jun 07, 2009 8:37 am**

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`

Posted: **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.

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.

Posted: **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

The 2nd MST is (1-2), (2-4), (3-4) and the cost is 1 + 20 + 1 = 22

So, the total cost is 34

Posted: **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?

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?

Posted: **Sun Jun 07, 2009 2:36 pm**

The problem statements say

So, it should be 34the total cost of this operation needs to be as small as possible