本文主要是介绍POJ3041 最小顶点覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
N*N的矩阵，有些格子有物体，每次消除一行或一列，最少要几次消灭完。
行i - >列j 连边，表示(i,j)处有物体，即 边表示 物体。
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;public class Main {public static void main(String[] args){new POJ3041().solve() ; }
}class POJ3041{InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final int N = 508 ;@SuppressWarnings("unchecked")List<Integer>[] g = new List[N<<1] ;int[] match = new int[N] ;boolean[] used = new boolean[N] ;boolean dfs(int u){for(int v : g[u]){if(used[v]) continue ;used[v] = true ;if(match[v] == -1 || dfs(match[v])){match[v] = u ;return true ; }}return false ;}int getMaxMatch(int n){int res = 0 ; Arrays.fill(match , -1) ;for(int i = 1 ; i <= n ; i++){Arrays.fill(used , false) ;if(dfs(i)) res++ ;}return res ;}void solve(){int n = in.nextInt() ;int m = in.nextInt() ;for(int i = 1 ; i <= n ; i++) g[i] = new ArrayList<Integer>() ; while(m-- > 0){g[in.nextInt()].add(in.nextInt()) ;}out.println(getMaxMatch(n)) ;out.flush() ;}}class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = new StringTokenizer(""); } private void eat(String s) { tokenizer = new StringTokenizer(s); } public String nextLine() { try { return reader.readLine(); } catch (Exception e) { return null; } } public boolean hasNext() { while (!tokenizer.hasMoreTokens()) { String s = nextLine(); if (s == null) return false; eat(s); } return true; } public String next() { hasNext(); return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } public long nextLong() { return Long.parseLong(next()); } public double nextDouble() { return Double.parseDouble(next()); } public BigInteger nextBigInteger() { return new BigInteger(next()); } } 这篇关于POJ3041 最小顶点覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
