POJ 3057 最大二分匹配+bfs + 二分

本文主要是介绍POJ 3057 最大二分匹配+bfs + 二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 Sample
Input
3
5 5
XXDXX
X...X
D...X
X...D
XXXXX
5 12
XXXXXXXXXXXX
X..........D
X.XXXXXXXXXX
X..........X
XXXXXXXXXXXX
5 5
XDXXX
X.X.D
XX.XX
D.X.X
XXXDX
Sample
Output
3
21
impossible

D 门

. 人

X 墙

门每分钟只能通过一个人，求最少时间所有人通过门。

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.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;public class Main {public static void main(String[] args){new POJ3057().solve()  ; }
}class POJ3057{InputReader in = new InputReader(System.in) ;PrintWriter out = new PrintWriter(System.out) ;final int W = 12 ;@SuppressWarnings("unchecked")List<Integer>[] g = new List[W*W*2] ;int[] match = new int[W*W*W*W*3] ;boolean[] used = new boolean[W*W*W*W*3] ;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 ;}final int inf = 0xfffffff ;char[][] wall = new char[W][W] ;int[][][][] dist = new int[W][W][W][W] ;List<Point> doors  ;List<Point> persons ;int n , m ; void solve(){int t = in.nextInt() ;while(t-- > 0){doors = new ArrayList<Point>() ;persons = new ArrayList<Point>() ; n = in.nextInt() ;m = in.nextInt() ;for(int i = 0 ; i < n ; i++) wall[i] = in.next().toCharArray() ;for(int i = 0 ; i < n ; i++){for(int j = 0 ; j < m ; j++){if(wall[i][j] == 'D') doors.add(new Point(i, j)) ;else if(wall[i][j] == '.') persons.add(new Point(i, j)) ;}}for(Point p : doors) bfs(p , dist[p.x][p.y]) ;int l = 0 , r = n*m+1 , res = -1 ;while(l <= r){int mid = (l + r) >> 1 ;if(judge(mid)){res = mid ;r = mid - 1 ;}else l = mid + 1 ;}if(res == -1) out.println("impossible") ;else out.println(res) ;}out.flush() ; }class Point{int x ;int y ;Point(int x , int y){this.x = x ;this.y = y ;}}int[][] dir = {{-1,0},{0,-1},{1,0},{0,1}} ;boolean can(int x , int y){return 0 <= x && x < n && 0 <= y && y < m ;}void bfs(Point start , int[][] dist){for(int i = 0 ; i < n ; i++)for(int j = 0 ; j < m ; j++) dist[i][j] = inf ; dist[start.x][start.y] = 0 ; Queue<Point> q = new LinkedList<Point>() ;q.add(start) ;while(! q.isEmpty()){Point u = q.poll() ;for(int i = 0 ; i < 4 ; i++){int x = u.x + dir[i][0] ;int y = u.y + dir[i][1] ;if(! can(x, y) || wall[x][y] != '.') continue ;if(dist[u.x][u.y] + 1 < dist[x][y]){dist[x][y] = dist[u.x][u.y] + 1 ;q.add(new Point(x, y)) ;}}}}boolean judge(int time){int p = persons.size() ; for(int i = 1 ; i <= p ; i++) g[i] = new ArrayList<Integer>() ; int d = doors.size() ;for(int i = 1 ; i <= p ; i++){Point person = persons.get(i-1) ;for(int j = 1 ; j <= d ; j++){Point door = doors.get(j-1) ;for(int t = dist[door.x][door.y][person.x][person.y] ; t <= time ; t++){g[i].add(p + (t-1) * d + j) ;}}}return getMaxMatch(p) == p ;}}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());  }  }