Code: Select all
code cut
Moderator: Board moderators
Code: Select all
code cut
Code: Select all
좋냐 심성일
Code: Select all
code removed after ACC
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;
}
}
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;
}
Code: Select all
AC
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
Code: Select all
2207 2211
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
Code: Select all
3956 3958
Code: Select all
Didn't really know what was wrong....