图论|ACM HDOJ 1151 (Air Raid) ACM|二分图

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1151
思路 DAG图（无回路有向图）的最小路径覆盖数 = 节点数 - 最大匹配数
程序一匈牙利算法 DFS

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int casesNumber = Integer.parseInt(scn.next()); while (0 <= --casesNumber) { int leftSetNumber = Integer.parseInt(scn.next()); int rightSetNumber = leftSetNumber; int edgesNumber = Integer.parseInt(scn.next()); Hungary hungary = new Hungary(leftSetNumber, rightSetNumber); for (int i = 0; i < edgesNumber; ++i) { int left = Integer.parseInt(scn.next()) - 1; int right = Integer.parseInt(scn.next()) - 1; hungary.addEdge(left, right); } System.out.println(leftSetNumber - hungary.maxMatch()); } scn.close(); }}class Hungary { private int leftSetNumber; private int rightSetNumber; private boolean[][] matrix; private int[] leftResult; private int[] rightResult; private boolean[] rightUsed; private boolean searchPath(int left) { for (int right = 0; right < rightSetNumber; ++right) { if (matrix[left][right] && !rightUsed[right]) { rightUsed[right] = true; if (-1 == rightResult[right] || searchPath(rightResult[right])) { rightResult[right] = left; leftResult[left] = right; return true; } } } return false; } public Hungary(int leftSetNumber, int rightSetNumber) { this.leftSetNumber = leftSetNumber; this.rightSetNumber = rightSetNumber; matrix = new boolean[leftSetNumber][rightSetNumber]; leftResult = new int[leftSetNumber]; rightResult = new int[rightSetNumber]; rightUsed = new boolean[rightSetNumber]; } public void addEdge(int left, int right) { matrix[left][right] = true; } public int maxMatch() { Arrays.fill(leftResult, -1); Arrays.fill(rightResult, -1); Arrays.fill(rightUsed, false); int count = 0; for (int left = 0; left < leftSetNumber; ++left) { if (-1 == leftResult[left]) { Arrays.fill(rightUsed, false); if (searchPath(left)) { ++count; } } } return count; }}

程序二匈牙利算法 BFS

import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int casesNumber = Integer.parseInt(scn.next()); while (0 <= --casesNumber) { int leftSetNumber = Integer.parseInt(scn.next()); int rightSetNumber = leftSetNumber; int edgesNumber = Integer.parseInt(scn.next()); Hungary hungary = new Hungary(leftSetNumber, rightSetNumber); for (int i = 0; i < edgesNumber; ++i) { int left = Integer.parseInt(scn.next()) - 1; int right = Integer.parseInt(scn.next()) - 1; hungary.addEdge(left, right); } System.out.println(leftSetNumber - hungary.maxMatch()); } scn.close(); }}class Hungary { private int leftSetNumber; private int rightSetNumber; private boolean[][] matrix; private int[] leftResult; private int[] rightResult; private boolean[] rightUsed; private int[] preLeft; public Hungary(int leftSetNumber, int rightSetNumber) { this.leftSetNumber = leftSetNumber; this.rightSetNumber = rightSetNumber; matrix = new boolean[leftSetNumber][rightSetNumber]; leftResult = new int[leftSetNumber]; rightResult = new int[rightSetNumber]; rightUsed = new boolean[rightSetNumber]; preLeft = new int[leftSetNumber]; } public void addEdge(int left, int right) { matrix[left][right] = true; } public int maxMatch() { Arrays.fill(leftResult, -1); Arrays.fill(rightResult, -1); Arrays.fill(preLeft, -1); int count = 0; for (int i = 0; i < leftSetNumber; ++i) { if (-1 == leftResult[i]) { Queue queue = new LinkedList(); queue.offer(i); boolean hasAP = false; Arrays.fill(rightUsed, false); while (!queue.isEmpty() && !hasAP) { int left = queue.poll(); for (int right = 0; right < rightSetNumber && !hasAP; ++right) { if (matrix[left][right] && !rightUsed[right]) { rightUsed[right] = true; queue.offer(rightResult[right]); if (0 <= rightResult[right]) { preLeft[rightResult[right]] = left; } else { hasAP = true; int currentLeft = left; int currentRight = right; while (-1 != currentLeft) { int lastRight = leftResult[currentLeft]; leftResult[currentLeft] = currentRight; rightResult[currentRight] = currentLeft; currentLeft = preLeft[currentLeft]; currentRight = lastRight; } } } } } if (-1 != leftResult[i]) { ++count; } } } return count; }}

【图论|ACM HDOJ 1151 (Air Raid)】程序三 Hopcroft-Carp 算法

import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int casesNumber = Integer.parseInt(scn.next()); while (0 <= --casesNumber) { int leftSetNumber = Integer.parseInt(scn.next()); int rightSetNumber = leftSetNumber; int edgesNumber = Integer.parseInt(scn.next()); HopcroftCarp hopcroftCarp = new HopcroftCarp(leftSetNumber, rightSetNumber); for (int i = 0; i < edgesNumber; ++i) { int left = Integer.parseInt(scn.next()) - 1; int right = Integer.parseInt(scn.next()) - 1; hopcroftCarp.addEdge(left, right); } System.out.println(leftSetNumber - hopcroftCarp.maxMatch()); } scn.close(); }}class HopcroftCarp { private final int INF = Integer.MAX_VALUE / 2; private int leftSetNumber; private int rightSetNumber; private boolean[][] matrix; private int[] leftResult; private int[] rightResult; private boolean[] rightUsed; private int[] leftGradation; private int[] rightGradation; private int gradation; private boolean searchPath() { Arrays.fill(leftGradation, -1); Arrays.fill(rightGradation, -1); gradation = INF; Queue queue = new LinkedList(); for (int left = 0; left < leftSetNumber; ++left) { if (-1 == leftResult[left]) { queue.offer(left); ++leftGradation[left]; } } while (!queue.isEmpty()) { int left = queue.poll(); if (leftGradation[left] > gradation) { break; } for (int right = 0; right < rightSetNumber; ++right) { if (matrix[left][right] && -1 == rightGradation[right]) { rightGradation[right] = leftGradation[left] + 1; if (-1 == rightResult[right]) { gradation = rightGradation[right]; } else { leftGradation[rightResult[right]] = rightGradation[right] + 1; queue.offer(rightResult[right]); } } } } return INF != gradation; } private boolean dfs(int left) { for (int right = 0; right < rightSetNumber; right++) { if (!rightUsed[right] && matrix[left][right] && rightGradation[right] == leftGradation[left] + 1) { rightUsed[right] = true; if (-1 != rightResult[right] && rightGradation[right] == gradation) { continue; } if (-1 == rightResult[right] || dfs(rightResult[right])) { rightResult[right] = left; leftResult[left] = right; return true; } } } return false; } public HopcroftCarp(int leftSetNumber, int rightSetNumber) { this.leftSetNumber = leftSetNumber; this.rightSetNumber = rightSetNumber; matrix = new boolean[leftSetNumber][rightSetNumber]; leftResult = new int[leftSetNumber]; rightResult = new int[rightSetNumber]; rightUsed = new boolean[rightSetNumber]; leftGradation = new int[leftSetNumber]; rightGradation = new int[rightSetNumber]; gradation = INF; } public void addEdge(int left, int right) { matrix[left][right] = true; } public int maxMatch() { Arrays.fill(leftResult, -1); Arrays.fill(rightResult, -1); int count = 0; while (searchPath()) { Arrays.fill(rightUsed, false); for (int left = 0; left < leftSetNumber; ++left) { if (-1 == leftResult[left] && dfs(left)) { ++count; } } } return count; }}