QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#478553#900. 一般图最大权匹配jxy2012#AC ✓284ms18376kbC++236.4kb2024-07-15 06:14:172024-07-15 06:14:18

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5900kb

input:

18 120
12 10 6
13 0 10
1 0 6
8 12 5
5 14 3
2 8 1
2 11 5
7 10 1
0 7 7
7 12 2
14 12 3
6 12 10
12 5 5
8 16 5
7 3 5
5 7 10
17 12 7
16 11 2
6 11 9
0 14 2
9 17 8
12 11 2
3 0 9
13 3 7
9 2 5
14 17 9
1 15 3
16 12 3
2 17 7
17 5 2
8 5 1
5 9 7
14 13 5
7 4 1
1 6 6
14 2 7
7 9 5
12 9 10
13 6 3
13 12 2
13 2 7
4 13 ...

output:

9 81
2 1
7 5
10 3
11 6
12 9
13 4
15 14
16 0
17 8

result:

ok OK: 9 matchings (cost = 81)

Test #2:

score: 0
Accepted
time: 26ms
memory: 15764kb

input:

500 499
0 1 389813
1 2 410923
1 3 255713
2 4 863533
2 5 274010
3 6 772811
3 7 347289
4 8 199232
4 9 235314
5 10 301630
5 11 993877
6 12 84918
6 13 888477
7 14 449408
7 15 916637
8 16 961209
8 17 550509
9 18 198289
9 19 686477
10 20 468966
10 21 274223
11 22 92197
11 23 463223
12 24 408479
12 25 7559...

output:

168 119581888
1 0
4 2
6 3
11 5
15 7
16 8
19 9
20 10
24 12
26 13
29 14
35 17
36 18
45 22
46 23
50 25
54 27
56 28
63 31
64 32
67 33
69 34
74 37
77 38
79 39
81 40
82 41
84 42
86 43
88 44
95 47
97 48
99 49
102 51
104 52
107 53
111 55
115 57
117 58
118 59
120 60
123 61
124 62
132 66
143 71
145 72
146 73
...

result:

ok OK: 168 matchings (cost = 119581888)

Test #3:

score: 0
Accepted
time: 185ms
memory: 16212kb

input:

500 124750
434 328 637504
128 157 89971
332 372 614087
326 76 853539
252 296 276599
10 272 491209
0 206 155108
199 370 435246
386 330 746983
445 399 229666
134 432 295002
129 221 287033
45 495 87615
283 272 442214
216 193 945283
400 374 84291
359 187 970582
269 487 595207
136 16 753522
201 365 85346...

output:

250 249209796
27 22
29 28
44 32
59 45
62 51
87 60
89 67
93 7
94 83
100 55
110 40
111 85
112 33
114 57
117 76
120 49
121 88
122 61
123 2
127 105
140 48
144 102
145 84
148 17
151 11
157 75
160 70
164 64
165 42
168 47
171 97
174 14
178 1
179 6
181 20
182 41
184 80
186 139
188 118
190 124
191 30
196 159...

result:

ok OK: 250 matchings (cost = 249209796)

Test #4:

score: 0
Accepted
time: 178ms
memory: 14412kb

input:

500 124750
478 344 670402
61 169 403144
226 362 582050
18 390 939395
368 496 106
167 99 320497
96 398 49834
152 153 399736
74 113 26602
194 186 182244
109 98 320637
139 65 981681
370 266 68504
370 385 563000
3 245 243216
404 418 676708
61 246 910028
230 319 359410
337 110 391826
168 405 284587
342 4...

output:

250 249190247
41 13
56 10
59 51
61 60
73 58
77 37
82 67
83 65
89 28
105 79
111 18
112 35
125 102
127 4
132 64
134 115
136 110
141 17
142 88
143 23
144 128
145 99
149 129
154 122
157 21
159 78
165 151
166 62
167 163
170 19
176 108
178 76
180 104
183 44
184 1
186 72
195 103
196 68
199 85
200 147
206 2...

result:

ok OK: 250 matchings (cost = 249190247)

Test #5:

score: 0
Accepted
time: 219ms
memory: 18376kb

input:

500 124750
69 2 176813
342 202 341146
243 316 341597
447 330 309751
67 438 255306
153 71 347111
460 431 415635
384 84 318379
309 162 533592
495 408 122486
465 385 328554
68 87 244852
307 123 261672
250 257 343542
0 321 339118
39 67 205003
203 183 393183
51 369 375752
444 251 243327
194 61 202474
288...

output:

250 124328901
33 4
35 7
37 14
59 2
90 10
98 71
109 31
110 60
115 0
125 102
127 3
130 113
135 92
139 15
147 106
150 81
154 87
155 77
157 19
158 136
159 74
162 101
169 57
173 97
178 149
180 172
183 48
184 46
186 160
190 62
191 99
196 32
207 58
208 36
209 63
210 153
215 6
216 40
217 124
218 104
219 146...

result:

ok OK: 250 matchings (cost = 124328901)

Test #6:

score: 0
Accepted
time: 213ms
memory: 16948kb

input:

500 124750
45 342 337395
390 38 389968
231 427 391488
458 482 345244
261 81 502109
206 128 476869
255 217 408094
226 422 316251
398 427 402011
382 50 382275
40 262 255568
324 451 95299
283 367 448216
95 420 228143
269 440 386095
91 370 302609
350 70 384538
90 244 409015
8 24 348278
337 198 412958
47...

output:

250 126736851
31 4
35 12
58 6
67 38
87 80
98 75
101 40
106 66
112 7
117 43
120 89
123 41
124 49
134 59
136 54
137 0
143 96
146 14
149 77
153 92
158 22
159 135
160 116
162 151
163 47
165 34
167 74
168 129
173 9
175 18
177 138
180 109
181 19
182 33
186 141
188 8
190 57
193 39
195 179
199 166
201 83
20...

result:

ok OK: 250 matchings (cost = 126736851)

Test #7:

score: 0
Accepted
time: 283ms
memory: 16464kb

input:

500 124750
20 91 407687
437 222 454355
397 116 711903
362 9 138631
135 468 171177
230 328 33032
76 414 656679
96 177 265906
236 425 563563
467 208 381861
461 360 408258
131 132 374158
436 206 209585
369 190 686727
269 32 495215
317 397 713616
158 30 219580
492 196 199829
231 153 526969
448 400 40114...

output:

250 135131415
43 37
45 41
53 50
54 11
68 34
75 71
84 13
87 86
88 76
94 46
95 27
105 4
110 91
111 70
112 24
114 64
118 79
123 19
125 73
130 117
132 17
136 113
142 140
144 36
146 67
148 124
150 44
152 15
158 116
164 29
168 59
170 82
172 85
175 16
176 48
180 106
184 89
188 3
193 135
195 72
196 145
197 ...

result:

ok OK: 250 matchings (cost = 135131415)

Test #8:

score: 0
Accepted
time: 284ms
memory: 16960kb

input:

500 124750
139 359 560822
416 164 355940
277 289 645310
247 229 308112
254 354 413387
325 201 345965
202 138 421169
0 96 326684
219 473 180133
313 271 613276
260 320 360483
311 78 280971
358 384 638695
276 89 220497
172 199 219619
363 214 462428
221 160 345988
457 100 364383
210 335 411879
408 127 1...

output:

250 137768547
16 11
28 18
33 0
43 26
55 6
67 27
69 47
76 23
77 9
82 65
89 31
94 22
95 38
102 50
104 88
113 68
124 35
127 100
130 17
132 83
134 21
139 44
140 10
141 87
145 39
148 86
151 103
154 12
155 138
157 108
164 73
165 42
167 4
170 131
175 136
176 59
178 158
179 114
181 70
185 111
190 101
194 15...

result:

ok OK: 250 matchings (cost = 137768547)

Test #9:

score: 0
Accepted
time: 26ms
memory: 16704kb

input:

500 509
28 29 798142
374 375 155108
465 466 67462
224 203 78421
427 428 473747
210 211 132772
244 245 365182
411 412 72018
14 15 755952
323 324 574820
6 7 550509
398 399 497268
246 247 911757
191 192 401127
92 93 735209
280 281 3728
329 330 149889
211 229 837178
395 396 128721
261 262 665820
80 81 5...

output:

229 143163175
1 0
3 2
5 4
7 6
9 8
11 10
13 12
15 14
17 16
19 18
21 20
23 22
25 24
28 27
30 29
32 31
34 33
36 35
38 37
40 39
42 41
44 43
46 45
48 47
50 49
52 51
54 53
57 56
59 58
61 60
63 62
66 65
68 67
71 70
73 72
75 74
77 76
79 78
81 80
84 83
86 85
88 87
89 64
93 92
96 95
98 97
100 99
102 101
104 1...

result:

ok OK: 229 matchings (cost = 143163175)

Test #10:

score: 0
Accepted
time: 1ms
memory: 5696kb

input:

7 8
2 0 1
0 5 2
5 6 3
6 1 4
1 0 5
1 3 6
3 4 7
1 4 8

output:

3 15
1 0
4 3
6 5

result:

ok OK: 3 matchings (cost = 15)

Test #11:

score: 0
Accepted
time: 1ms
memory: 5612kb

input:

4 3
0 2 1
1 3 1
1 2 3

output:

1 3
2 1

result:

ok OK: 1 matchings (cost = 3)

Test #12:

score: 0
Accepted
time: 52ms
memory: 14696kb

input:

500 18491
0 41 255713
0 42 863533
0 43 274010
0 44 772811
0 45 347289
0 46 199232
0 47 235314
0 48 301630
0 49 993877
0 50 84918
0 51 888477
0 52 449408
0 53 916637
0 54 961209
0 55 550509
0 56 198289
0 57 686477
0 58 468966
0 59 274223
0 60 92197
0 61 463223
0 62 408479
0 63 755952
0 64 992057
0 65...

output:

246 236805997
41 39
42 25
43 23
44 2
45 17
46 27
47 1
48 6
49 30
50 22
51 13
52 26
53 5
54 16
55 4
56 18
57 38
58 21
59 28
60 9
61 10
62 36
63 24
64 0
65 3
66 14
67 32
68 8
69 34
70 37
71 15
72 31
73 40
74 29
75 35
76 19
77 11
78 20
79 7
80 12
81 33
123 112
124 88
125 94
126 100
127 115
128 122
129 ...

result:

ok OK: 246 matchings (cost = 236805997)

Test #13:

score: 0
Accepted
time: 0ms
memory: 5752kb

input:

14 17
0 1 1
2 3 1
4 5 1
6 7 1
8 9 1
10 11 1
1 3 1
7 9 1
0 13 1
6 12 1
1 2 1
3 4 1
0 6 1
7 8 1
9 10 1
5 13 1
11 12 1

output:

7 7
2 1
4 3
6 0
8 7
10 9
12 11
13 5

result:

ok OK: 7 matchings (cost = 7)

Test #14:

score: 0
Accepted
time: 0ms
memory: 8396kb

input:

100 4782
1 0 836156
0 2 650307
3 0 919221
4 0 949862
5 0 698275
0 6 852060
7 0 969823
0 8 976873
9 0 920939
0 10 961872
11 0 792805
12 0 783792
13 0 847080
14 0 966134
0 15 620555
16 0 660641
0 17 698789
0 18 839783
19 0 840533
20 0 803432
21 0 936205
0 22 597688
0 23 790583
24 0 807247
25 0 768673
...

output:

50 48814559
10 0
14 7
19 13
23 11
26 17
29 8
38 15
40 32
43 25
44 4
46 22
49 35
50 3
51 37
53 31
54 28
57 47
59 12
60 1
61 16
62 45
64 18
65 30
66 2
67 5
68 52
69 6
71 63
74 39
76 41
77 24
78 34
79 27
80 56
81 20
83 82
84 72
85 55
87 48
88 9
89 36
90 21
92 86
93 70
94 42
95 91
96 33
97 58
98 75
99 73

result:

ok OK: 50 matchings (cost = 48814559)

Test #15:

score: 0
Accepted
time: 96ms
memory: 14492kb

input:

500 17707
328 434 346246
157 128 880874
372 332 491081
326 76 447517
252 296 631603
272 10 529316
206 0 904903
199 370 7430
386 330 834552
445 399 672655
432 134 47985
129 221 925946
495 45 10646
272 283 805709
216 193 654458
374 400 102357
359 187 276657
269 487 309604
16 136 588531
201 365 218178
...

output:

250 244194530
18 17
57 36
65 14
74 58
86 82
91 44
92 1
94 45
99 89
109 54
111 88
114 22
118 35
127 100
129 121
142 29
143 9
145 40
147 67
148 136
150 70
151 33
153 62
159 149
162 122
167 125
168 146
171 144
172 47
173 64
176 4
182 51
183 130
184 48
186 71
187 81
189 75
191 34
199 170
202 52
206 20
2...

result:

ok OK: 250 matchings (cost = 244194530)

Test #16:

score: 0
Accepted
time: 219ms
memory: 16276kb

input:

500 69830
478 344 670402
61 169 403144
226 362 582050
18 390 939395
368 496 106
167 99 320497
96 398 49834
152 153 399736
74 113 26602
194 186 182244
109 98 320637
139 65 981681
370 266 68504
370 385 563000
3 245 243216
404 418 676708
61 246 910028
230 319 359410
337 110 391826
168 405 284587
342 46...

output:

250 248580250
23 2
36 17
56 10
61 60
66 43
73 58
76 54
92 41
98 83
100 30
117 115
127 4
132 64
133 102
138 82
142 88
143 24
149 129
154 122
157 21
159 78
161 26
165 151
166 141
168 22
170 19
174 35
176 108
180 104
184 37
188 84
192 139
195 103
196 68
199 144
200 147
206 44
207 16
208 12
209 93
212 1...

result:

ok OK: 250 matchings (cost = 248580250)

Test #17:

score: 0
Accepted
time: 1ms
memory: 5552kb

input:

1 0

output:

0 0

result:

ok OK: 0 matchings (cost = 0)

Test #18:

score: 0
Accepted
time: 1ms
memory: 5648kb

input:

12 45
0 9 9
10 3 8
2 6 5
6 9 1
7 4 5
8 0 5
11 2 3
9 10 3
0 2 9
10 11 3
8 10 10
1 3 7
9 4 1
6 5 9
5 9 8
9 11 10
1 5 6
1 11 6
2 3 1
7 0 6
7 9 1
7 3 8
5 0 9
11 4 9
3 8 6
5 2 4
0 10 4
7 6 5
11 3 10
8 2 8
10 6 9
8 9 3
11 6 3
0 3 2
11 7 5
10 4 5
8 6 7
9 1 1
8 5 2
1 8 5
7 10 4
5 10 9
4 6 2
4 8 2
5 7 4

output:

6 50
2 0
3 1
6 5
7 4
10 8
11 9

result:

ok OK: 6 matchings (cost = 50)

Test #19:

score: 0
Accepted
time: 1ms
memory: 5648kb

input:

7 11
5 2 10
1 4 1
3 5 8
1 5 2
1 3 8
5 6 2
0 3 7
0 1 5
2 0 4
5 0 2
2 4 6

output:

3 19
1 0
4 2
5 3

result:

ok OK: 3 matchings (cost = 19)

Test #20:

score: 0
Accepted
time: 25ms
memory: 13984kb

input:

500 693
434 328 637504
128 157 89971
332 372 614087
326 76 853539
252 296 276599
10 272 491209
0 206 155108
199 370 435246
386 330 746983
445 399 229666
134 432 295002
129 221 287033
45 495 87615
283 272 442214
216 193 945283
400 374 84291
359 187 970582
269 487 595207
136 16 753522
201 365 853460
6...

output:

208 140607212
30 0
53 18
72 8
85 31
89 82
91 42
93 84
96 70
100 92
104 39
111 108
119 55
129 57
134 133
136 16
147 46
150 37
153 67
156 15
157 130
164 25
167 75
169 163
174 165
175 143
188 38
195 172
199 179
203 138
208 86
210 48
211 63
213 2
214 6
216 193
223 54
228 187
230 66
232 191
237 26
240 11...

result:

ok OK: 208 matchings (cost = 140607212)

Test #21:

score: 0
Accepted
time: 15ms
memory: 14344kb

input:

500 198
478 344 670402
61 169 403144
226 362 582050
18 390 939395
368 496 106
167 99 320497
96 398 49834
152 153 399736
74 113 26602
194 186 182244
109 98 320637
139 65 981681
370 266 68504
370 385 563000
3 245 243216
404 418 676708
61 246 910028
230 319 359410
337 110 391826
168 405 284587
342 467 ...

output:

115 69723351
52 6
53 34
63 39
71 0
91 72
130 88
134 97
139 121
146 28
148 77
149 67
153 152
157 108
159 44
166 13
175 50
176 3
183 89
186 96
193 100
199 125
203 123
215 171
223 216
224 222
227 65
228 140
232 191
236 27
246 61
247 244
257 56
260 201
261 231
267 113
268 29
269 45
271 2
274 182
276 167...

result:

ok OK: 115 matchings (cost = 69723351)

Test #22:

score: 0
Accepted
time: 8ms
memory: 14076kb

input:

500 88
281 268 424379
393 269 569773
293 112 820473
154 69 556134
172 56 555523
254 72 988419
231 355 399670
445 197 657413
365 320 505284
228 426 6938
475 392 572337
448 167 59585
395 239 326937
38 398 830787
407 181 29235
109 137 810927
286 132 637780
471 425 91601
241 261 565168
307 177 54898
232...

output:

70 35935997
45 24
81 19
118 12
121 16
137 109
154 69
158 63
172 56
200 119
205 55
220 58
221 123
230 217
232 151
254 72
260 245
261 241
263 223
268 42
275 25
276 168
277 50
286 132
290 4
293 112
305 20
306 89
307 36
333 326
335 195
340 271
341 258
342 91
345 88
350 71
351 77
355 174
363 107
364 255
...

result:

ok OK: 70 matchings (cost = 35935997)

Test #23:

score: 0
Accepted
time: 30ms
memory: 14536kb

input:

500 1217
328 387 666424
250 126 238859
199 140 793606
383 409 328902
91 466 815857
368 268 832378
204 165 119357
276 65 25913
24 332 675150
314 385 955116
145 270 784426
72 238 210996
448 162 145634
263 269 60681
197 438 448379
478 83 910787
178 375 590129
143 296 645764
185 184 208561
463 411 73770...

output:

236 176065026
20 17
46 32
53 8
56 3
68 65
70 25
74 4
88 11
91 1
96 37
105 19
107 35
111 75
120 54
121 51
125 102
126 31
128 95
133 92
136 79
138 77
142 12
148 117
150 71
151 137
158 106
161 48
167 157
170 72
172 83
175 171
182 93
184 62
186 113
189 76
190 50
195 147
196 129
199 29
205 112
208 169
21...

result:

ok OK: 236 matchings (cost = 176065026)

Test #24:

score: 0
Accepted
time: 21ms
memory: 15124kb

input:

500 532
391 107 385798
204 138 601057
231 468 613601
76 171 107831
100 401 518399
409 28 566973
153 401 96171
284 46 816233
37 472 585755
347 385 828772
146 205 553619
28 126 454201
220 136 233919
7 301 545967
202 13 323656
37 222 947061
394 329 365417
174 175 931822
26 294 67332
223 265 147197
23 2...

output:

192 125667090
45 34
61 3
73 54
77 72
80 67
85 38
90 71
93 48
100 97
105 95
107 66
114 91
116 41
121 76
125 96
134 31
137 40
145 63
148 104
154 103
165 47
168 78
169 17
172 146
175 122
176 162
178 87
179 106
186 118
187 0
191 53
192 65
196 143
197 13
198 183
202 29
203 190
207 8
208 117
211 127
213 2...

result:

ok OK: 192 matchings (cost = 125667090)