@Test public void basicTest() { for (int n = 4; n <= 16; n += 2) { for (int k = 1; k <= n / 2; k++) { int[][] relationship = new int[n][n]; if (!fullfill(relationship, k, n)) continue; Assert.assertEquals(true, PerfectMatchingInKBipartite.solve(relationship, k)); System.out.println("pass " + n + "," + k); } } }
public static boolean solve(int[][] relationships, int k) { int n = relationships.length; assert n % 2 == 0; int[][] flowGraph = new int[n + 2][n + 2]; for (int i = 0; i < n / 2; i++) { flowGraph[n][i] = 1; } for (int i = n / 2; i < n; i++) { flowGraph[i][n + 1] = 1; } for (int i = 0; i < n / 2; i++) { int cnt = 0; for (int j = n / 2; j < n; j++) { if (relationships[i][j] == 0) continue; flowGraph[i][j] = Integer.MAX_VALUE; cnt++; } assert cnt == k; } int[] pre = new int[n + 2]; int res = fordFulkerson(flowGraph, n, n + 1, pre); System.out.println(res); return res == n / 2; }
PerfectMatchingInKBipartite { public static boolean solve(int[][] relationships, int k) { int n = relationships.length; assert n % 2 == 0; int[][] flowGraph = new int[n + 2][n + 2]; for (int i = 0; i < n / 2; i++) { flowGraph[n][i] = 1; } for (int i = n / 2; i < n; i++) { flowGraph[i][n + 1] = 1; } for (int i = 0; i < n / 2; i++) { int cnt = 0; for (int j = n / 2; j < n; j++) { if (relationships[i][j] == 0) continue; flowGraph[i][j] = Integer.MAX_VALUE; cnt++; } assert cnt == k; } int[] pre = new int[n + 2]; int res = fordFulkerson(flowGraph, n, n + 1, pre); System.out.println(res); return res == n / 2; } }
PerfectMatchingInKBipartite { public static boolean solve(int[][] relationships, int k) { int n = relationships.length; assert n % 2 == 0; int[][] flowGraph = new int[n + 2][n + 2]; for (int i = 0; i < n / 2; i++) { flowGraph[n][i] = 1; } for (int i = n / 2; i < n; i++) { flowGraph[i][n + 1] = 1; } for (int i = 0; i < n / 2; i++) { int cnt = 0; for (int j = n / 2; j < n; j++) { if (relationships[i][j] == 0) continue; flowGraph[i][j] = Integer.MAX_VALUE; cnt++; } assert cnt == k; } int[] pre = new int[n + 2]; int res = fordFulkerson(flowGraph, n, n + 1, pre); System.out.println(res); return res == n / 2; }  }
PerfectMatchingInKBipartite { public static boolean solve(int[][] relationships, int k) { int n = relationships.length; assert n % 2 == 0; int[][] flowGraph = new int[n + 2][n + 2]; for (int i = 0; i < n / 2; i++) { flowGraph[n][i] = 1; } for (int i = n / 2; i < n; i++) { flowGraph[i][n + 1] = 1; } for (int i = 0; i < n / 2; i++) { int cnt = 0; for (int j = n / 2; j < n; j++) { if (relationships[i][j] == 0) continue; flowGraph[i][j] = Integer.MAX_VALUE; cnt++; } assert cnt == k; } int[] pre = new int[n + 2]; int res = fordFulkerson(flowGraph, n, n + 1, pre); System.out.println(res); return res == n / 2; }  static boolean solve(int[][] relationships, int k); }
PerfectMatchingInKBipartite { public static boolean solve(int[][] relationships, int k) { int n = relationships.length; assert n % 2 == 0; int[][] flowGraph = new int[n + 2][n + 2]; for (int i = 0; i < n / 2; i++) { flowGraph[n][i] = 1; } for (int i = n / 2; i < n; i++) { flowGraph[i][n + 1] = 1; } for (int i = 0; i < n / 2; i++) { int cnt = 0; for (int j = n / 2; j < n; j++) { if (relationships[i][j] == 0) continue; flowGraph[i][j] = Integer.MAX_VALUE; cnt++; } assert cnt == k; } int[] pre = new int[n + 2]; int res = fordFulkerson(flowGraph, n, n + 1, pre); System.out.println(res); return res == n / 2; }  static boolean solve(int[][] relationships, int k);  }