1const NEG_INF: i64 = i64::MIN / 2;
2
3#[derive(Debug, Clone)]
4pub struct GeneralWeightedMatching {
5 size: usize,
6 weight: Vec<Vec<i64>>,
7 mate: Vec<usize>,
8 matching_weight: i64,
9}
10
11impl GeneralWeightedMatching {
12 pub fn new(size: usize) -> Self {
13 Self {
14 size,
15 weight: vec![vec![NEG_INF; size]; size],
16 mate: vec![!0; size],
17 matching_weight: NEG_INF,
18 }
19 }
20 pub fn add_edge(&mut self, u: usize, v: usize, w: i64) {
21 assert!(u < self.size);
22 assert!(v < self.size);
23 if u == v {
24 return;
25 }
26 if w > self.weight[u][v] {
27 self.weight[u][v] = w;
28 self.weight[v][u] = w;
29 self.matching_weight = NEG_INF;
30 }
31 }
32 pub fn from_edges(size: usize, edges: &[(usize, usize, i64)]) -> Self {
33 let mut gm = Self::new(size);
34 for &(u, v, w) in edges {
35 gm.add_edge(u, v, w);
36 }
37 gm
38 }
39 pub fn maximum_weight_matching(&mut self) -> (i64, Vec<(usize, usize)>) {
40 self.compute();
41 let mut res = Vec::with_capacity(self.size / 2);
42 for v in 0..self.size {
43 let u = self.mate[v];
44 if u != !0 && v < u {
45 res.push((v, u));
46 }
47 }
48 (self.matching_weight, res)
49 }
50 fn compute(&mut self) {
51 if self.matching_weight != NEG_INF {
52 return;
53 }
54 let n = self.size;
55 if n == 0 {
56 self.matching_weight = 0;
57 return;
58 }
59 let mut edges = Vec::new();
60 let mut weights = Vec::new();
61 let mut neighbend = vec![Vec::new(); n];
62 for i in 0..n {
63 for j in i + 1..n {
64 let w = self.weight[i][j];
65 if w == NEG_INF {
66 continue;
67 }
68 let k = weights.len();
69 weights.push(w);
70 edges.push(i);
71 edges.push(j);
72 neighbend[i].push(2 * k + 1);
73 neighbend[j].push(2 * k);
74 }
75 }
76 let m = weights.len();
77 if m == 0 {
78 self.mate.fill(!0);
79 self.matching_weight = 0;
80 return;
81 }
82 let mut blossom = BlossomMatching::new(n, edges, weights, neighbend);
83 blossom.solve(false);
84 self.mate.fill(!0);
85 let mut total = 0i64;
86 for v in 0..n {
87 let u = blossom.mate[v];
88 if u != !0 && v < u {
89 self.mate[v] = u;
90 self.mate[u] = v;
91 total += self.weight[v][u];
92 }
93 }
94 self.matching_weight = total;
95 }
96}
97
98struct BlossomMatching {
99 n: usize,
100 endpoint: Vec<usize>,
101 weight: Vec<i64>,
102 neighbend: Vec<Vec<usize>>,
103 mate: Vec<usize>,
104 label: Vec<i32>,
105 labelend: Vec<usize>,
106 inblossom: Vec<usize>,
107 blossomparent: Vec<usize>,
108 blossomchilds: Vec<Vec<usize>>,
109 blossombase: Vec<usize>,
110 blossomendps: Vec<Vec<usize>>,
111 bestedge: Vec<usize>,
112 blossombestedges: Vec<Vec<usize>>,
113 unusedblossoms: Vec<usize>,
114 dualvar: Vec<i64>,
115 allowedge: Vec<bool>,
116 queue: Vec<usize>,
117}
118
119impl BlossomMatching {
120 fn new(n: usize, endpoint: Vec<usize>, weight: Vec<i64>, neighbend: Vec<Vec<usize>>) -> Self {
121 let mut maxweight = 0i64;
122 for &w in &weight {
123 maxweight = maxweight.max(w);
124 }
125 let mate = vec![!0; n];
126 let label = vec![0i32; 2 * n];
127 let labelend = vec![!0; 2 * n];
128 let mut inblossom = vec![0usize; n];
129 let blossomparent = vec![!0; 2 * n];
130 let blossomchilds = vec![Vec::new(); 2 * n];
131 let mut blossombase = vec![!0; 2 * n];
132 let blossomendps = vec![Vec::new(); 2 * n];
133 let bestedge = vec![!0; 2 * n];
134 let blossombestedges = vec![Vec::new(); 2 * n];
135 let mut unusedblossoms = Vec::new();
136 for v in 0..n {
137 inblossom[v] = v;
138 blossombase[v] = v;
139 }
140 for b in n..2 * n {
141 unusedblossoms.push(b);
142 }
143 let mut dualvar = vec![0i64; 2 * n];
144 for dv in dualvar.iter_mut().take(n) {
145 *dv = maxweight;
146 }
147 let allowedge = vec![false; weight.len()];
148 let queue = Vec::new();
149 Self {
150 n,
151 endpoint,
152 weight,
153 neighbend,
154 mate,
155 label,
156 labelend,
157 inblossom,
158 blossomparent,
159 blossomchilds,
160 blossombase,
161 blossomendps,
162 bestedge,
163 blossombestedges,
164 unusedblossoms,
165 dualvar,
166 allowedge,
167 queue,
168 }
169 }
170
171 fn slack(&self, k: usize) -> i64 {
172 let i = self.endpoint[2 * k];
173 let j = self.endpoint[2 * k + 1];
174 self.dualvar[i] + self.dualvar[j] - 2 * self.weight[k]
175 }
176
177 fn blossom_leaves(&self, b: usize, out: &mut Vec<usize>) {
178 if b < self.n {
179 out.push(b);
180 } else {
181 for &t in &self.blossomchilds[b] {
182 if t < self.n {
183 out.push(t);
184 } else {
185 self.blossom_leaves(t, out);
186 }
187 }
188 }
189 }
190
191 fn assign_label(&mut self, w: usize, t: i32, p: usize) {
192 let b = self.inblossom[w];
193 self.label[w] = t;
194 self.label[b] = t;
195 self.labelend[w] = p;
196 self.labelend[b] = p;
197 self.bestedge[w] = !0;
198 self.bestedge[b] = !0;
199 if t == 1 {
200 let mut leaves = Vec::new();
201 self.blossom_leaves(b, &mut leaves);
202 for v in leaves {
203 self.queue.push(v);
204 }
205 } else {
206 let base = self.blossombase[b];
207 let m = self.mate[base];
208 if m == !0 {
209 return;
210 }
211 let u = self.endpoint[m];
212 self.assign_label(u, 1, m ^ 1);
213 }
214 }
215
216 fn scan_blossom(&mut self, mut v: usize, mut w: usize) -> usize {
217 let mut path: Vec<usize> = Vec::new();
218 let mut base = !0;
219 while v != !0 || w != !0 {
220 let b = self.inblossom[v];
221 if (self.label[b] & 4) != 0 {
222 base = self.blossombase[b];
223 break;
224 }
225 path.push(b);
226 self.label[b] = 5;
227 if self.labelend[b] == !0 {
228 v = !0;
229 } else {
230 v = self.endpoint[self.labelend[b]];
231 let b2 = self.inblossom[v];
232 v = self.endpoint[self.labelend[b2]];
233 }
234 if w != !0 {
235 std::mem::swap(&mut v, &mut w);
236 }
237 }
238 for b in path {
239 self.label[b] = 1;
240 }
241 base
242 }
243
244 fn add_blossom(&mut self, base: usize, k: usize) {
245 let mut v = self.endpoint[2 * k];
246 let mut w = self.endpoint[2 * k + 1];
247 let bb = self.inblossom[base];
248 let mut bv = self.inblossom[v];
249 let mut bw = self.inblossom[w];
250 let b = self.unusedblossoms.pop().unwrap();
251 self.blossombase[b] = base;
252 self.blossomparent[b] = !0;
253 self.blossomparent[bb] = b;
254 self.blossomchilds[b].clear();
255 self.blossomendps[b].clear();
256 let mut path: Vec<usize> = Vec::new();
257 let mut endps: Vec<usize> = Vec::new();
258 while bv != bb {
259 self.blossomparent[bv] = b;
260 path.push(bv);
261 endps.push(self.labelend[bv]);
262 v = self.endpoint[self.labelend[bv]];
263 bv = self.inblossom[v];
264 }
265 path.push(bb);
266 path.reverse();
267 self.blossomchilds[b] = path.clone();
268 endps.reverse();
269 endps.push(2 * k);
270 self.blossomendps[b] = endps.clone();
271 while bw != bb {
272 self.blossomparent[bw] = b;
273 path.push(bw);
274 self.blossomchilds[b] = path.clone();
275 endps.push(self.labelend[bw] ^ 1);
276 self.blossomendps[b] = endps.clone();
277 w = self.endpoint[self.labelend[bw]];
278 bw = self.inblossom[w];
279 }
280 self.label[b] = 1;
281 self.labelend[b] = self.labelend[bb];
282 self.dualvar[b] = 0;
283 let mut leaves = Vec::new();
284 self.blossom_leaves(b, &mut leaves);
285 for v in leaves {
286 if self.label[self.inblossom[v]] == 2 {
287 self.queue.push(v);
288 }
289 self.inblossom[v] = b;
290 }
291 let mut bestedgeto = vec![!0; 2 * self.n];
292 for &bv in &path {
293 let nblists: Vec<Vec<usize>> = if self.blossombestedges[bv].is_empty() {
294 let mut lists = Vec::new();
295 let mut leaves = Vec::new();
296 self.blossom_leaves(bv, &mut leaves);
297 for v in leaves {
298 let mut list = Vec::new();
299 let neigh = self.neighbend[v].clone();
300 for p in neigh {
301 list.push(p / 2);
302 }
303 lists.push(list);
304 }
305 lists
306 } else {
307 vec![self.blossombestedges[bv].clone()]
308 };
309 for nblist in nblists {
310 for k in nblist {
311 let mut i = self.endpoint[2 * k];
312 let mut j = self.endpoint[2 * k + 1];
313 if self.inblossom[j] == b {
314 std::mem::swap(&mut i, &mut j);
315 }
316 let bj = self.inblossom[j];
317 if bj != b
318 && self.label[bj] == 1
319 && (bestedgeto[bj] == !0 || self.slack(k) < self.slack(bestedgeto[bj]))
320 {
321 bestedgeto[bj] = k;
322 }
323 }
324 }
325 self.blossombestedges[bv].clear();
326 self.bestedge[bv] = !0;
327 }
328 self.blossombestedges[b].clear();
329 for k in bestedgeto {
330 if k != !0 {
331 self.blossombestedges[b].push(k);
332 }
333 }
334 self.bestedge[b] = !0;
335 for &k in &self.blossombestedges[b] {
336 if self.bestedge[b] == !0 || self.slack(k) < self.slack(self.bestedge[b]) {
337 self.bestedge[b] = k;
338 }
339 }
340 }
341
342 fn step_index(len: usize, j: usize, forward: bool) -> usize {
343 if forward {
344 let next = j + 1;
345 if next == len { 0 } else { next }
346 } else if j == 0 {
347 len - 1
348 } else {
349 j - 1
350 }
351 }
352
353 fn dec_index(len: usize, j: usize) -> usize {
354 if j == 0 { len - 1 } else { j - 1 }
355 }
356
357 fn expand_blossom(&mut self, b: usize, endstage: bool) {
358 let childs = self.blossomchilds[b].clone();
359 for s in childs {
360 self.blossomparent[s] = !0;
361 if s < self.n {
362 self.inblossom[s] = s;
363 } else if endstage && self.dualvar[s] == 0 {
364 self.expand_blossom(s, endstage);
365 } else {
366 let mut leaves = Vec::new();
367 self.blossom_leaves(s, &mut leaves);
368 for v in leaves {
369 self.inblossom[v] = s;
370 }
371 }
372 }
373 if !endstage && self.label[b] == 2 {
374 let entrychild = {
375 let p = self.labelend[b];
376 let u = self.endpoint[p ^ 1];
377 self.inblossom[u]
378 };
379 let len = self.blossomchilds[b].len();
380 let mut j = self.blossomchilds[b]
381 .iter()
382 .position(|&x| x == entrychild)
383 .unwrap();
384 let forward = j % 2 == 1;
385 let endptrick = if forward { 0usize } else { 1usize };
386 let mut p = self.labelend[b];
387 while j != 0 {
388 let v1 = self.endpoint[p ^ 1];
389 self.label[v1] = 0;
390 let idx = if endptrick == 0 {
391 j
392 } else {
393 Self::dec_index(len, j)
394 };
395 let tmp = self.blossomendps[b][idx];
396 let v2 = self.endpoint[(tmp ^ endptrick) ^ 1];
397 self.label[v2] = 0;
398 self.assign_label(v1, 2, p);
399 let tmp = self.blossomendps[b][idx];
400 self.allowedge[tmp / 2] = true;
401 j = Self::step_index(len, j, forward);
402 let idx2 = if endptrick == 0 {
403 j
404 } else {
405 Self::dec_index(len, j)
406 };
407 let tmp2 = self.blossomendps[b][idx2];
408 p = tmp2 ^ endptrick;
409 self.allowedge[p / 2] = true;
410 j = Self::step_index(len, j, forward);
411 }
412 let bv = self.blossomchilds[b][j];
413 let v1 = self.endpoint[p ^ 1];
414 self.label[v1] = 2;
415 self.label[bv] = 2;
416 self.labelend[v1] = p;
417 self.labelend[bv] = p;
418 self.bestedge[bv] = !0;
419 j = Self::step_index(len, j, forward);
420 loop {
421 let tmpb = self.blossomchilds[b][j];
422 if tmpb == entrychild {
423 break;
424 }
425 let bv = tmpb;
426 if self.label[bv] == 1 {
427 j = Self::step_index(len, j, forward);
428 continue;
429 }
430 let mut reached: Option<usize> = None;
431 let mut leaves = Vec::new();
432 self.blossom_leaves(bv, &mut leaves);
433 for v in leaves {
434 if self.label[v] != 0 {
435 reached = Some(v);
436 break;
437 }
438 }
439 if let Some(v) = reached {
440 self.label[v] = 0;
441 let base = self.blossombase[bv];
442 let m = self.mate[base];
443 self.label[self.endpoint[m]] = 0;
444 self.assign_label(v, 2, self.labelend[v]);
445 }
446 j = Self::step_index(len, j, forward);
447 }
448 }
449 self.label[b] = -1;
450 self.labelend[b] = !0;
451 self.blossomchilds[b].clear();
452 self.blossomendps[b].clear();
453 self.blossombase[b] = !0;
454 self.blossombestedges[b].clear();
455 self.bestedge[b] = !0;
456 self.unusedblossoms.push(b);
457 }
458
459 fn augment_blossom(&mut self, b: usize, v: usize) {
460 let mut t = v;
461 while self.blossomparent[t] != b {
462 t = self.blossomparent[t];
463 }
464 if t >= self.n {
465 self.augment_blossom(t, v);
466 }
467 let len = self.blossomchilds[b].len();
468 let i = self.blossomchilds[b].iter().position(|&x| x == t).unwrap();
469 let mut j = i;
470 let forward = i % 2 == 1;
471 let endptrick = if forward { 0usize } else { 1usize };
472 while j != 0 {
473 j = Self::step_index(len, j, forward);
474 let t = self.blossomchilds[b][j];
475 let pidx = if endptrick == 0 {
476 j
477 } else {
478 Self::dec_index(len, j)
479 };
480 let p = self.blossomendps[b][pidx] ^ endptrick;
481 if t >= self.n {
482 self.augment_blossom(t, self.endpoint[p]);
483 }
484 j = Self::step_index(len, j, forward);
485 let t2 = self.blossomchilds[b][j];
486 if t2 >= self.n {
487 self.augment_blossom(t2, self.endpoint[p ^ 1]);
488 }
489 self.mate[self.endpoint[p]] = p ^ 1;
490 self.mate[self.endpoint[p ^ 1]] = p;
491 }
492 let mut new_child = vec![0usize; len];
493 for (idx, &val) in self.blossomchilds[b].iter().enumerate() {
494 let pos = (idx + len - i) % len;
495 new_child[pos] = val;
496 }
497 self.blossomchilds[b] = new_child;
498 let mut new_endps = vec![0usize; len];
499 for (idx, &val) in self.blossomendps[b].iter().enumerate() {
500 let pos = (idx + len - i) % len;
501 new_endps[pos] = val;
502 }
503 self.blossomendps[b] = new_endps;
504 self.blossombase[b] = self.blossombase[self.blossomchilds[b][0]];
505 }
506
507 fn augment_matching(&mut self, k: usize) {
508 let v = self.endpoint[2 * k];
509 let w = self.endpoint[2 * k + 1];
510 for (s, p) in [(v, 2 * k + 1), (w, 2 * k)] {
511 let mut s = s;
512 let mut p = p;
513 loop {
514 let bs = self.inblossom[s];
515 if bs >= self.n {
516 self.augment_blossom(bs, s);
517 }
518 self.mate[s] = p;
519 if self.labelend[bs] == !0 {
520 break;
521 }
522 let t = self.endpoint[self.labelend[bs]];
523 let bt = self.inblossom[t];
524 let s2 = self.endpoint[self.labelend[bt]];
525 let j = self.endpoint[self.labelend[bt] ^ 1];
526 if bt >= self.n {
527 self.augment_blossom(bt, j);
528 }
529 self.mate[j] = self.labelend[bt];
530 p = self.labelend[bt] ^ 1;
531 s = s2;
532 }
533 }
534 }
535
536 fn solve(&mut self, maxcardinality: bool) {
537 for _ in 0..self.n {
538 self.label.fill(0);
539 self.bestedge.fill(!0);
540 for b in self.n..2 * self.n {
541 self.blossombestedges[b].clear();
542 }
543 self.allowedge.fill(false);
544 self.queue.clear();
545 for v in 0..self.n {
546 if self.mate[v] == !0 && self.label[self.inblossom[v]] == 0 {
547 self.assign_label(v, 1, !0);
548 }
549 }
550 let mut augmented = false;
551 loop {
552 while let Some(v) = self.queue.pop() {
553 if self.label[self.inblossom[v]] != 1 {
554 continue;
555 }
556 let neigh = self.neighbend[v].clone();
557 for p in neigh {
558 let k = p / 2;
559 let w = self.endpoint[p];
560 if self.inblossom[v] == self.inblossom[w] {
561 continue;
562 }
563 let mut kslack = 0i64;
564 if !self.allowedge[k] {
565 kslack = self.slack(k);
566 if kslack <= 0 {
567 self.allowedge[k] = true;
568 }
569 }
570 if self.allowedge[k] {
571 if self.label[self.inblossom[w]] == 0 {
572 self.assign_label(w, 2, p ^ 1);
573 } else if self.label[self.inblossom[w]] == 1 {
574 let base = self.scan_blossom(v, w);
575 if base != !0 {
576 self.add_blossom(base, k);
577 } else {
578 self.augment_matching(k);
579 augmented = true;
580 break;
581 }
582 } else if self.label[w] == 0 {
583 self.label[w] = 2;
584 self.labelend[w] = p ^ 1;
585 }
586 } else if self.label[self.inblossom[w]] == 1 {
587 let b = self.inblossom[v];
588 if self.bestedge[b] == !0 || kslack < self.slack(self.bestedge[b]) {
589 self.bestedge[b] = k;
590 }
591 } else if self.label[w] == 0
592 && (self.bestedge[w] == !0 || kslack < self.slack(self.bestedge[w]))
593 {
594 self.bestedge[w] = k;
595 }
596 }
597 if augmented {
598 break;
599 }
600 }
601 if augmented {
602 break;
603 }
604 let mut deltatype = -1;
605 let mut delta = 0i64;
606 let mut deltaedge = !0;
607 let mut deltablossom = !0;
608 if !maxcardinality {
609 deltatype = 1;
610 delta = self.dualvar[0..self.n].iter().cloned().min().unwrap_or(0);
611 }
612 for v in 0..self.n {
613 if self.label[self.inblossom[v]] == 0 && self.bestedge[v] != !0 {
614 let d = self.slack(self.bestedge[v]);
615 if deltatype == -1 || d < delta {
616 delta = d;
617 deltatype = 2;
618 deltaedge = self.bestedge[v];
619 }
620 }
621 }
622 for b in 0..2 * self.n {
623 if self.blossomparent[b] == !0 && self.label[b] == 1 && self.bestedge[b] != !0 {
624 let kslack = self.slack(self.bestedge[b]);
625 let d = kslack / 2;
626 if deltatype == -1 || d < delta {
627 delta = d;
628 deltatype = 3;
629 deltaedge = self.bestedge[b];
630 }
631 }
632 }
633 for b in self.n..2 * self.n {
634 if self.blossombase[b] != !0
635 && self.blossomparent[b] == !0
636 && self.label[b] == 2
637 && (deltatype == -1 || self.dualvar[b] < delta)
638 {
639 delta = self.dualvar[b];
640 deltatype = 4;
641 deltablossom = b;
642 }
643 }
644 if deltatype == -1 {
645 if maxcardinality {
646 deltatype = 1;
647 delta = 0.max(*self.dualvar[0..self.n].iter().min().unwrap_or(&0));
648 } else {
649 break;
650 }
651 }
652 for v in 0..self.n {
653 if self.label[self.inblossom[v]] == 1 {
654 self.dualvar[v] -= delta;
655 } else if self.label[self.inblossom[v]] == 2 {
656 self.dualvar[v] += delta;
657 }
658 }
659 for b in self.n..2 * self.n {
660 if self.blossombase[b] != !0 && self.blossomparent[b] == !0 {
661 if self.label[b] == 1 {
662 self.dualvar[b] += delta;
663 } else if self.label[b] == 2 {
664 self.dualvar[b] -= delta;
665 }
666 }
667 }
668 if deltatype == 1 {
669 break;
670 } else if deltatype == 2 {
671 let k = deltaedge;
672 self.allowedge[k] = true;
673 let mut i = self.endpoint[2 * k];
674 let mut j = self.endpoint[2 * k + 1];
675 if self.label[self.inblossom[i]] == 0 {
676 std::mem::swap(&mut i, &mut j);
677 }
678 self.queue.push(i);
679 } else if deltatype == 3 {
680 let k = deltaedge;
681 self.allowedge[k] = true;
682 let i = self.endpoint[2 * k];
683 self.queue.push(i);
684 } else if deltatype == 4 {
685 self.expand_blossom(deltablossom, false);
686 }
687 }
688 if !augmented {
689 break;
690 }
691 for b in self.n..2 * self.n {
692 if self.blossomparent[b] == !0
693 && self.blossombase[b] != !0
694 && self.label[b] == 1
695 && self.dualvar[b] == 0
696 {
697 self.expand_blossom(b, true);
698 }
699 }
700 }
701 for v in 0..self.n {
702 if self.mate[v] != !0 {
703 self.mate[v] = self.endpoint[self.mate[v]];
704 }
705 }
706 }
707}
708
709#[cfg(test)]
710mod tests {
711 use super::*;
712 use crate::{rand, tools::Xorshift};
713
714 fn brute(n: usize, edges: &[(usize, usize, i64)]) -> i64 {
715 let mut w = vec![vec![NEG_INF; n]; n];
716 for &(u, v, c) in edges {
717 w[u][v] = w[u][v].max(c);
718 w[v][u] = w[v][u].max(c);
719 }
720 let mut dp = vec![NEG_INF; 1 << n];
721 dp[0] = 0;
722 for mask in 1usize..1 << n {
723 let i = mask.trailing_zeros() as usize;
724 let mask_without_i = mask & !(1 << i);
725 let mut best = dp[mask_without_i];
726 let mut m = mask_without_i;
727 while m != 0 {
728 let j = m.trailing_zeros() as usize;
729 if w[i][j] != NEG_INF {
730 let val = w[i][j] + dp[mask_without_i & !(1 << j)];
731 if val > best {
732 best = val;
733 }
734 }
735 m &= m - 1;
736 }
737 dp[mask] = best;
738 }
739 dp[(1 << n) - 1]
740 }
741
742 #[test]
743 fn test_general_weighted_matching() {
744 const Q: usize = 200;
745 const N: usize = 10;
746 let mut rng = Xorshift::default();
747 for _ in 0..Q {
748 rand!(rng, n: 1..=N);
749 let mut edges = vec![];
750 for i in 0..n {
751 for j in i + 1..n {
752 rand!(rng, b: 0..3usize);
753 if b != 0 {
754 rand!(rng, w: 1..=100i64);
755 edges.push((i, j, w));
756 }
757 }
758 }
759 let mut gm = GeneralWeightedMatching::from_edges(n, &edges);
760 let (ans, matching) = gm.maximum_weight_matching();
761 let mut used = vec![false; n];
762 let mut sum = 0i64;
763 let mut adj = vec![vec![NEG_INF; n]; n];
764 for &(u, v, w) in &edges {
765 adj[u][v] = adj[u][v].max(w);
766 adj[v][u] = adj[v][u].max(w);
767 }
768 for &(u, v) in &matching {
769 assert!(u < v);
770 assert!(adj[u][v] != NEG_INF);
771 assert!(!used[u]);
772 assert!(!used[v]);
773 used[u] = true;
774 used[v] = true;
775 sum += adj[u][v];
776 }
777 assert_eq!(ans, sum);
778 assert_eq!(ans, brute(n, &edges));
779 }
780 }
781}