pat1001. Battle Over Cities - Hard Version 解题报告

98 阅读 0 评论 65 点赞

我是靠谱客的博主典雅大雁，这篇文章主要介绍pat1001. Battle Over Cities - Hard Version 解题报告，现在分享给大家，希望可以做个参考。

/**
题目：删去一个点，然后求出需要增加最小代价的边集合生成连通图
思路：
prim+最小堆
1.之前图中未破坏的边必用，从而把两两之间可互达的点集合合并成一个点
2.求出不同点集合的最短距离，用prim+最小堆求出最小生成树

kruskal
1.之前图中未破坏的边必用，全部加到图中
2.途中被破坏的边按照边权从小到大的顺序依次加入图中，直到图变为连通图

两个方法的对应一个点的最小生成树的复杂度都是nlogm，第二个方法较好写

优化：
1.未破坏的边直接加入图中
2.当有n-2条边(当前删去一个点后，图中n-1个点)在图中时，直接结束建生成树

另外：
求图的连通性：
有向强连通
无向并查集

当然，并查集好写很多。。。
**/

复制代码

1 #include <stdio.h>

2 #include <stdlib.h>

3 #define maxn 500

4 #define maxm 125000

5 #define maxdist 100000

7 /**

8 题目：删去一个点，然后求出需要增加最小代价的边集合生成连通图

9 思路：
 10 prim+最小堆
 11 1.之前图中未破坏的边必用，从而把两两之间可互达的点集合 合并成一个点
 12 2.求出不同点集合的最短距离，用prim+最小堆求出最小生成树
 13
 14 kruskal
 15 1.之前图中未破坏的边必用，全部加到图中
 16 2.途中被破坏的边按照边权从小到大的顺序依次加入图中，直到图变为连通图
 17
 18 两个方法的对应一个点的最小生成树的复杂度都是nlogm，第二个方法较好写
 19
 20 优化：
 21 1.未破坏的边直接加入图中
 22 2.当有n-2条边(当前删去一个点后，图中n-1个点)在图中时，直接结束建生成树
 23
 24 另外：
 25 求图的连通性：
 26 有向 强连通
 27 无向 并查集
 28
 29 当然，并查集好写很多。。。
 30 **/
 31
 32 struct node
 33 {
 34
long x,y,c,s;
 35 }edge0[maxm+1],edge1[maxm+1];
 36 long fa[maxn+1];
 37
 38 long max(long a,long b)
 39 {
 40
if (a>b)
 41
return a;
 42
else
 43
return b;
 44 }
 45
 46 int cmp(const void *a,const void *b)
 47 {
 48
//先把未损坏的路径加入图中
 49
if ((*(struct node *)a).s < (*(struct node *)b).s)
 50
return 1;
 51
else if ((*(struct node *)a).s > (*(struct node *)b).s)
 52
return -1;
 53
//再对已损坏的路径进行排序，用kruskal算法,m log m
 54
else if ((*(struct node *)a).c < (*(struct node *)b).c)
 55
return 1;
 56
else
 57
return -1;
 58 }
 59
 60 long getfather(long d)
 61 {
 62
if (fa[d]==d)
 63
return d;
 64
else
 65
return getfather(fa[d]);
 66 }
 67
 68 int main()
 69 {
 70
long i,j,n,m,p,q,x,y,c,s,g,fx,fy,ans,cost[maxn+1];
 71
while (scanf("%ld%ld",&n,&m)!=EOF)
 72 
{
 73
p=0;
 74
q=0;
 75
for (i=0;i<m;i++)
 76 
{
 77
scanf("%ld%ld%ld%ld",&x,&y,&c,&s);
 78
if (s==1)
 79 
{
 80
p++;
 81
edge1[p].x=x; edge1[p].y=y; edge1[p].c=c; edge1[p].s=s;
 82 
}
 83
else
 84 
{
 85
q++;
 86
edge0[q].x=x; edge0[q].y=y; edge0[q].c=c; edge0[q].s=s;
 87 
}
 88 
}
 89
qsort(edge0+1,q,sizeof(struct node),cmp);
 90
 91
ans=0;
 92
for (i=1;i<=n;i++)
 93 
{
 94
for (j=1;j<=n;j++)
 95
fa[j]=j;
 96
g=0;
 97
//edge - exist
 98
for (j=1;j<=p;j++)
 99 
{
100
if (edge1[j].x==i || edge1[j].y==i) continue;
101
fx=getfather(edge1[j].x);
102
fy=getfather(edge1[j].y);
103
if (fx==fy) continue;
104
fa[fx]=fy;
105
g++;
106
if (g==n-2)
107
break;
108 
}
109
//优化
110
if (g==n-2)
111 
{
112
cost[i]=0;
113
continue;
114 
}
115
116
//edge - not exist
117
cost[i]=0;
118
for (j=1;j<=q;j++)
119 
{
120
if (edge0[j].x==i || edge0[j].y==i) continue;
121
fx=getfather(edge0[j].x);
122
fy=getfather(edge0[j].y);
123
if (fx==fy) continue;
124
fa[fx]=fy;
125
g++;
126
cost[i]+=edge0[j].c;
127
//优化
128
if (g==n-2)
129
break;
130 
}
131
if (g<n-2)
132
cost[i]=maxdist;
133
ans=max(ans,cost[i]);
134 
}
135
if (ans>0)
136 
{
137
for (i=1;i<=n;i++)
138
if (cost[i]==ans)
139 
{
140
printf("%ld",i);
141
break;
142 
}
143
for (j=i+1;j<=n;j++)
144
if (cost[j]==ans)
145
printf(" %ld",j);
146
printf("n");
147 
}
148
else
149
printf("0n");
150 
}
151
return 0;
152 }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260

1 #include <stdio.h>

2 #include <stdlib.h>

3 #define maxn 500

4 #define maxm 125000

5 #define maxdist 100000

6

7 /**

8 题目：删去一个点，然后求出需要增加最小代价的边集合生成连通图

9 思路：
 10 prim+最小堆
 11 1.之前图中未破坏的边必用，从而把两两之间可互达的点集合 合并成一个点
 12 2.求出不同点集合的最短距离，用prim+最小堆求出最小生成树
 13
 14 kruskal
 15 1.之前图中未破坏的边必用，全部加到图中
 16 2.途中被破坏的边按照边权从小到大的顺序依次加入图中，直到图变为连通图
 17
 18 两个方法的对应一个点的最小生成树的复杂度都是nlogm，第二个方法较好写
 19
 20 优化：
 21 1.未破坏的边直接加入图中
 22 2.当有n-2条边(当前删去一个点后，图中n-1个点)在图中时，直接结束建生成树
 23
 24 另外：
 25 求图的连通性：
 26 有向 强连通
 27 无向 并查集
 28
 29 当然，并查集好写很多。。。
 30 **/
 31
 32 struct node
 33 {
 34
long x,y,c,s;
 35 }edge0[maxm+1],edge1[maxm+1];
 36 long fa[maxn+1];
 37
 38 long max(long a,long b)
 39 {
 40
if (a>b)
 41
return a;
 42
else
 43
return b;
 44 }
 45
 46 int cmp(const void *a,const void *b)
 47 {
 48
//先把未损坏的路径加入图中
 49
if ((*(struct node *)a).s < (*(struct node *)b).s)
 50
return 1;
 51
else if ((*(struct node *)a).s > (*(struct node *)b).s)
 52
return -1;
 53
//再对已损坏的路径进行排序，用kruskal算法,m log m
 54
else if ((*(struct node *)a).c < (*(struct node *)b).c)
 55
return 1;
 56
else
 57
return -1;
 58 }
 59
 60 long getfather(long d)
 61 {
 62
if (fa[d]==d)
 63
return d;
 64
else
 65
return getfather(fa[d]);
 66 }
 67
 68 int main()
 69 {
 70
long i,j,n,m,p,q,x,y,c,s,g,fx,fy,ans,cost[maxn+1];
 71
while (scanf("%ld%ld",&n,&m)!=EOF)
 72 
{
 73
p=0;
 74
q=0;
 75
for (i=0;i<m;i++)
 76 
{
 77
scanf("%ld%ld%ld%ld",&x,&y,&c,&s);
 78
if (s==1)
 79 
{
 80
p++;
 81
edge1[p].x=x; edge1[p].y=y; edge1[p].c=c; edge1[p].s=s;
 82 
}
 83
else
 84 
{
 85
q++;
 86
edge0[q].x=x; edge0[q].y=y; edge0[q].c=c; edge0[q].s=s;
 87 
}
 88 
}
 89
qsort(edge0+1,q,sizeof(struct node),cmp);
 90
 91
ans=0;
 92
for (i=1;i<=n;i++)
 93 
{
 94
for (j=1;j<=n;j++)
 95
fa[j]=j;
 96
g=0;
 97
//edge - exist
 98
for (j=1;j<=p;j++)
 99 
{
100
if (edge1[j].x==i || edge1[j].y==i) continue;
101
fx=getfather(edge1[j].x);
102
fy=getfather(edge1[j].y);
103
if (fx==fy) continue;
104
fa[fx]=fy;
105
g++;
106
if (g==n-2)
107
break;
108 
}
109
//优化
110
if (g==n-2)
111 
{
112
cost[i]=0;
113
continue;
114 
}
115
116
//edge - not exist
117
cost[i]=0;
118
for (j=1;j<=q;j++)
119 
{
120
if (edge0[j].x==i || edge0[j].y==i) continue;
121
fx=getfather(edge0[j].x);
122
fy=getfather(edge0[j].y);
123
if (fx==fy) continue;
124
fa[fx]=fy;
125
g++;
126
cost[i]+=edge0[j].c;
127
//优化
128
if (g==n-2)
129
break;
130 
}
131
if (g<n-2)
132
cost[i]=maxdist;
133
ans=max(ans,cost[i]);
134 
}
135
if (ans>0)
136 
{
137
for (i=1;i<=n;i++)
138
if (cost[i]==ans)
139 
{
140
printf("%ld",i);
141
break;
142 
}
143
for (j=i+1;j<=n;j++)
144
if (cost[j]==ans)
145
printf(" %ld",j);
146
printf("n");
147 
}
148
else
149
printf("0n");
150 
}
151
return 0;
152 }