10600 - ACM Contest and Blackout

[sds1100]

I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code: Select all

code cut

I got ac oh ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

[tmdrbs6584]

Code: Select all

좋냐 심성일

[little joey]

This is a public forum, so please post in English.

[sumantbhardvaj]

I tried to implement the algorithm mentioned in cormen for finding the second best minimum spanning tree . (along with prims to find minimum spanning tree ) but it is giving wrong answer in 0.029 secs..

some body plz provide me with some test cases or have a look at my code..

Code: Select all

code removed after ACC

[sumantbhardvaj]

got ACC

changed it from PRIMS to Kruskal ..

[little joey]

remove your code, then

[renato_ferreira]

Hi, I am getting WA for this problem, but my code is right for the inputs.

Code: Select all

#include <stdio.h>

#define INF 2100100100
#define MAXVERTICES 500
#define MAXARESTAS MAXVERTICES * MAXVERTICES

typedef struct
{
    int u, v, c;
}
Aresta;

typedef enum
{
    FALSE = 0, TRUE
}
boolean;

int pai[MAXVERTICES], rank[MAXVERTICES];
Aresta aresta[MAXARESTAS];
boolean flag[MAXARESTAS];

int arestas, vertices;

void MakeSet(int x);
int FindSet(int x);
void Union(int x, int y);

int cmp(Aresta *a, Aresta *b);

int kruskal(int retira);

int main(int argc, char **argv)
{
    int casos;

    scanf(" %d", &casos);

    while (casos--)
    {
        int i, ArvGeradora = 0, SegundaArv = INF;

        scanf(" %d %d", &vertices, &arestas);

        for (i = 1; i <= arestas; i++)
        {
            int u, v, c;

            flag[i] = FALSE;
            MakeSet(i);

            scanf(" %d %d %d", &u, &v, &c);

            aresta[i].u = u;
            aresta[i].v = v;
            aresta[i].c = c;
        }

        qsort(aresta, arestas + 1, sizeof(Aresta), cmp);

        for (i = 1; i <= arestas; i++)
        {}

        for (i = 1; i <= arestas; i++)
        {
            if (FindSet(aresta[i].u) != FindSet(aresta[i].v))
            {
                Union(aresta[i].u, aresta[i].v);

                ArvGeradora += aresta[i].c;
                flag[i] = TRUE;
            }
        }

        for (i = 1; i <= arestas; i++)
        {
            int j;

            for (j = 1; j <= arestas; j++)
            {
                MakeSet(j);
            }

            if (flag[i])
            {
                int temp = kruskal(i);

                if (temp < SegundaArv)
                {
                    SegundaArv = temp;
                }
            }
        }

        printf("%d %d\n", ArvGeradora, SegundaArv);
    }

    return 0;
}

void MakeSet(int x)
{
    pai[x] = x;
    rank[x] = 1;
}

int FindSet(int x)
{
    if (x != pai[x])
    {
        pai[x] = FindSet(pai[x]);
    }

    return pai[x];
}

void Union(int x, int y)
{
    x = FindSet(x);
    y = FindSet(y);

    if (rank[x] > rank[y])
    {
        pai[y] = x;
        rank[x] += rank[y];
    }

    else
    {
        pai[x] = y;
        rank[y] += rank[x];
    }
}

int cmp(Aresta *a, Aresta *b)
{
    return a->c - b->c;
}

int kruskal(int retira)
{
    int i, somaPesos = 0, cont = 0;

    for (i = 1; i <= arestas; i++)
    {
        if (FindSet(aresta[i].u) != FindSet(aresta[i].v) && i != retira)
        {
            Union(aresta[i].u, aresta[i].v);

            somaPesos += aresta[i].c;
            cont++;
        }
    }

    if (cont >= (vertices - 1))
    {
        return somaPesos;
    }

    else
    {
        return INF;
    }
}

Thanks.

[mohsincsedu]

After TLE....

I got WA....


need some io..



here is my code:

Code: Select all

#include <stdio.h>
#include <stdlib.h>


#define INF 10000

typedef struct st
{
	int weight;
	int v1,v2;
}edges;

st e[305],sav[305];
int nver,nedges,u[105],v[105],used[105],uused[105];
char intree[500];


int Min(int a,int b)
{
	if(a<b)
		return a;
	else
		return b;
}


int compare(const void* a, const void* b)
{
	edges *a1, *b1;
	a1 = (edges*)a; b1 = (edges*)b;
	if (a1[0].weight > b1[0].weight)
		return 1;
	return -1;
}

int istreedone()
{
	int ii; 
	char c = intree[0];
	for (ii=0;ii<nver;ii++)
		if (intree[ii] == 0)
			return 0;
	for (ii=1;ii<nver;ii++)
		if (intree[ii] != c)
			return 0;
	return 1;
}

int kruskal()
{
	int ii,jj,color,cur,toconvert,index;
	int total;
	qsort(e,nedges,sizeof(edges),compare);
	for (ii=0;ii<nver;ii++)
	{
		intree[ii] = 0;
		used[ii] = 0;
	}
	ii = 0; color = 1; total = 0,index = 0;
	while (istreedone()==0)
	{
		if (intree[e[ii].v1]!=intree[e[ii].v2])
		{
			if (intree[e[ii].v1] > intree[e[ii].v2])
			{
				cur = intree[e[ii].v1]; toconvert = e[ii].v2;
			}
			else
			{
				cur = intree[e[ii].v2]; toconvert = e[ii].v1;
			}
			total += e[ii].weight;
			/*u[index] = e[ii].v1;
			v[index] = e[ii].v2;
			index++;*/
			used[ii] = 1;
			if (intree[toconvert] == 0)
			{
				intree[toconvert] = cur;
			}
			else
			{
				toconvert = intree[toconvert];
				for (jj=0;jj<nver;jj++)
					if (intree[jj] == toconvert)
						intree[jj] = cur;
			}
		}
		else
		{
			if (intree[e[ii].v1]==0 && intree[e[ii].v2] == 0){
				intree[e[ii].v1] = color;
				intree[e[ii].v2] = color;
				total+= e[ii].weight;
				/*u[index] = e[ii].v1;
				v[index] = e[ii].v2;
				index++;*/
				used[ii] = 1;
				color++;
			}
		}
		ii++;
	}
	return total;
}


int main()
{
	int nCase,i,min,cost,temp,j;
	//freopen("kruskal.in","r",stdin);
	scanf("%d",&nCase);


	while(nCase--)
	{
		scanf("%d %d",&nver,&nedges);
		for(i = 0;i<nedges;i++)
		{
			scanf("%d %d %d",&e[i].v1,&e[i].v2,&e[i].weight);
			e[i].v1--;
			e[i].v2--;
		}
		cost = kruskal();
		min = INF;
		for(i = 0;i<nedges;i++)
			uused[i] = used[i];
		
		for(i = 0;i<nedges;i++)
		{
			if(uused[i])
			{
				for(j = 0;j<nedges;j++)
				{
					sav[j].v1 = e[j].v1;
					sav[j].v2 = e[j].v2;
					sav[j].weight = e[j].weight;
				}
				
				e[i].weight = INF;
				temp = kruskal();
				
				min = Min(min,temp);
				for(j = 0;j<nedges;j++)
				{
					e[j].v1 = sav[j].v1;
					e[j].v2 =  sav[j].v2;
					e[j].weight = sav[j].weight;
				}
				
			}
		}
		
		if(cost>min||min==INF)
			min = cost;
		printf("%d %d\n",cost,min);
		
		
	}



	
	return 0;
}

Thanks in advanced...

[mohsincsedu]

what is the output of the following input?
1
2 1
1 2 3

I think the output should be: 3 3

is it ok??

[mmfrb]

Why WA?

Code: Select all

AC

[mmfrb]

No one? Please? I dunno what I can change anymore..

[brianfry713]

Input:

Code: Select all

1
33 89
1 11 236
1 29 209
1 32 53
2 10 43
2 4 142
2 9 148
3 19 148
3 30 80
3 4 243
4 12 201
5 20 253
6 24 126
6 33 86
6 4 51
7 11 117
7 11 290
7 26 158
7 31 270
7 32 11
7 32 119
8 20 199
8 33 209
8 5 74
9 16 64
9 18 119
9 20 44
10 28 145
11 12 198
11 17 36
11 18 100
12 32 235
12 6 297
12 7 127
12 7 90
13 16 153
14 26 76
15 23 95
15 5 92
16 10 143
16 6 125
17 24 100
17 5 173
18 25 265
18 31 234
18 8 292
19 10 43
19 29 220
20 25 228
20 3 222
20 32 227
21 17 84
21 22 133
21 23 18
22 20 25
22 26 85
23 14 264
23 4 128
23 5 124
24 4 100
24 6 209
24 8 16
25 26 25
25 9 205
26 12 104
26 13 166
27 16 37
27 20 179
28 11 286
28 11 36
28 11 5
28 16 212
28 27 107
28 29 255
29 27 218
29 9 180
30 10 108
30 10 211
30 18 171
30 26 33
31 10 187
31 12 167
31 18 296
31 32 183
31 9 171
32 25 218
32 25 276
32 25 80
33 16 53
33 5 173

AC output:

Code: Select all

2207 2211

[mmfrb]

Yes! Your sample input made me think that the number of disjoint sets before and after has to be the same! Now i got AC... thanks so so so much!

[brianfry713]

Input:

Code: Select all

1
47 102
44 46 262
21 11 190
42 44 27
2 27 121
4 15 193
17 30 246
7 8 287
1 29 244
19 8 196
33 2 42
11 40 191
47 23 36
43 27 268
22 27 139
36 34 127
44 26 136
5 41 202
33 11 99
20 11 169
21 17 1
14 37 31
36 6 236
41 22 35
47 6 154
33 18 250
12 33 117
31 17 13
20 34 184
30 25 155
25 39 132
40 39 223
24 1 140
46 36 268
4 18 191
21 22 224
32 41 259
2 9 46
35 7 171
39 37 29
30 19 115
47 21 170
1 36 188
15 18 101
32 41 227
7 16 156
26 3 16
34 26 240
19 12 183
8 16 243
5 29 39
25 44 119
39 5 71
10 15 25
29 23 68
24 34 157
5 24 138
30 20 283
41 21 200
36 10 124
43 16 262
18 31 144
1 45 98
15 38 209
37 24 250
3 41 59
26 44 262
45 24 166
45 17 168
7 27 244
2 24 121
11 5 162
34 10 92
3 32 296
26 43 24
45 35 208
41 3 50
44 22 217
13 2 102
18 2 186
21 37 163
25 46 72
13 26 31
23 6 162
18 26 241
5 36 231
7 1 93
28 39 15
9 6 229
10 43 86
26 39 10
24 16 209
2 28 31
33 27 173
12 27 243
47 32 296
27 34 36
18 29 130
2 47 37
44 8 134
14 34 260
8 33 38
36 14 281

AC output:

Code: Select all

3956 3958

[afruizc]

I have solved this problem, but I'm getting RTE.
I've used the next procedure:
For the first MST, simply run kruskal and print the MST value, also every time an edge is added to the Tree, I add it to a vector to keep track of it later. After this process, I take every one of the edges, I flag the edge being processed and I run MST ignoring the flagged edge. Then, among all the MST I pick the least one.
Here is my code.
After some debugging and thanks to the help of Brianfry713, I've found that the exception is trown un line 57 when processing the previous I/O, with a value of j=7 and w = 128.

Here is my code:

Code: Select all

Didn't really know what was wrong....

I'd really appreciate any help that could be given to me