-
Notifications
You must be signed in to change notification settings - Fork 1
/
MaxMatchingRandomized.java
64 lines (55 loc) · 1.24 KB
/
MaxMatchingRandomized.java
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
package Matching;
import java.util.*;
public class MaxMatchingRandomized {
static final int MOD = 29989;
static int pow(int a, int b) {
int res = 1;
for (; b > 0; b >>= 1) {
if ((b & 1) != 0)
res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
static int rank(int[][] a) {
int r = 0;
int n = a.length;
for (int j = 0; j < n; j++) {
int k;
for (k = r; k < n && a[k][j] == 0; k++)
;
if (k == n)
continue;
int[] t = a[r];
a[r] = a[k];
a[k] = t;
int inv = pow(a[r][j], MOD - 2);
for (int i = j; i < n; i++)
a[r][i] = a[r][i] * inv % MOD;
for (int u = r + 1; u < n; u++)
for (int v = j + 1; v < n; v++)
a[u][v] = (a[u][v] - a[r][v] * a[u][j] % MOD + MOD) % MOD;
++r;
}
return r;
}
public static int maxMatching(boolean[][] d) {
int n = d.length;
int[][] a = new int[n][n];
Random rnd = new Random(1);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (d[i][j]) {
a[i][j] = rnd.nextInt(MOD - 1) + 1;
a[j][i] = MOD - a[i][j];
}
}
}
return rank(a) / 2;
}
// Usage example
public static void main(String[] args) {
int res = maxMatching(new boolean[][] { { false, true }, { true, false } });
System.out.println(1 == res);
}
}