图论练习5

Going Home

Here

解题思路

$KM$ 模板
二分图最优匹配，前提是有完美匹配（即存在一一配对）
左右集合分别有顶标 $lx[i],ly[j]$ ，当 $lx[i]+ly[j]=w[i][j]$ 时， $i\rightarrow j$ 为有效边，即选中
初始 $lx[i]=-inf,ly[j]=0$
对于左集合每个点，选择其连边中最优的， $lx[i]=Max\ w$
然后对于每个点找其最优匹配
若能在前面连好边的图中找到匹配，则继续下一个点
若不能，考虑撤销边
如何撤销？
对于这次找增广路左集合中的点，找一条不在这条增广路上的边，进行替换
找到最小代价，即 $d=Min\ lx[i]+ly[j]-w[i][j]$
对于这次找增广路访问到的左集合 $lx[i]-d$ ，右集合 $ly[j]+d$
重复进行，直到实现该点找到增广路可以添入或不能进行替换（无完美匹配）
对于该题，求最小，只用将距离变为负值，最后结果在反回来
每次找增广路前清空 $visx[],viy[]$


import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;










//implements Runnable
public class Main{
	static long md=(long)998244353;
	static long Linf=Long.MAX_VALUE/2;
	static int inf=Integer.MAX_VALUE/2;
	static int N=200;
	
	static
	class Node{
		int x;
		int y;
		public Node(int u,int v) {
			x=u;
			y=v;
		}
	}
	static int[][] w=new int[N+1][N+1];
	static void getw(Node a,Node b,int i,int j) {
		w[i][j]=-(Math.abs(a.x-b.x)+Math.abs(a.y-b.y));
	}
	static int mm=0;
	static int hh=0;
	static int[] lx=new int[N+1];
	static int[] ly=new int[N+1];
	static int[] link=new int[N+1];
	static boolean[] visx=new boolean[N+1];
	static boolean[] visy=new boolean[N+1];
	static Node[] men=new Node[N+1];
	static Node[] home=new Node[N+1];
	static boolean dfs(int x) {
		visx[x]=true;
		for(int i=1;i<=hh;++i) {
			if(!visy[i]&&lx[x]+ly[i]==w[x][i]) {
				visy[i]=true;
				if(link[i]==0||dfs(link[i])) {
					link[i]=x;
					return true;
				}
			}
		}
		return false;
	}
	static void solve() throws Exception{
		AReader input=new AReader();
	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));	
	    while(true) {
	    	int n=input.nextInt();
		    int m=input.nextInt();
		    if(n==0&&m==0)break;
		    mm=0;
		    hh=0;
		    Arrays.fill(link, 0);
		    for(int i=1;i<=n;++i) {
		    	String string=" "+input.next();
		    	char[] mp=string.toCharArray();
		    	for(int j=1;j<mp.length;++j) {
		    		if(mp[j]=='m') {
		    			mm++;
		    			men[mm]=new Node(i, j);
		    		}else if(mp[j]=='H') {
		    			hh++;
		    			home[hh]=new Node(i, j);
		    		}
		    	}
		    }
		    for(int i=1;i<=mm;++i){
		    	for(int j=1;j<=hh;++j) {
		    		getw(men[i], home[j], i, j);
		    	}
		    }
		    
		    for(int i=1;i<=mm;++i) {
		    	lx[i]=-inf;
		    	for(int j=1;j<=hh;++j) {
		    		ly[j]=0;
		    		lx[i]=Math.max(lx[i], w[i][j]);
		    	}
		    }
		    boolean ok=true;
		    for(int i=1;i<=mm;++i) {
		    	
		    	while(true) {//对于当前点i找个匹配,一直试
		    		Arrays.fill(visx, false);
			    	Arrays.fill(visy, false);
			    	int dis=inf;
			    	if(dfs(i))break;
			    	//直接不能找到
			    	//考虑改边
			    	for(int j=1;j<=mm;++j) {
			    		if(!visx[j]) continue;
			    		for(int k=1;k<=hh;++k) {
			    			if(visy[k])continue;
			    			dis=Math.min(dis, (lx[j]+ly[k])-w[j][k]);
			    		}
			    	}
			    	if(dis==inf) {
			    		ok=false;
			    		break;
			    	}
			    	for(int j=1;j<=mm;++j)if(visx[j])lx[j]-=dis;
			    	for(int j=1;j<=hh;++j)if(visy[j])ly[j]+=dis;
		    	}
		    	if(!ok)break;
		    }
		    int sum=0;
		   if(ok) {
			   for(int i=1;i<=hh;++i) {
				   sum-=w[link[i]][i];
			   }
			   out.println(sum);
		   }else out.println(-1);
	    }
	    
 	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
		solve();
	}
//	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Main(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}
		static
		class AReader{ 
		    BufferedReader bf;
		    StringTokenizer st;
		    BufferedWriter bw;

		    public AReader(){
		        bf=new BufferedReader(new InputStreamReader(System.in));
		        st=new StringTokenizer("");
		        bw=new BufferedWriter(new OutputStreamWriter(System.out));
		    }
		    public String nextLine() throws IOException{
		        return bf.readLine();
		    }
		    public String next() throws IOException{
		        while(!st.hasMoreTokens()){
		            st=new StringTokenizer(bf.readLine());
		        }
		        return st.nextToken();
		    }
		    public char nextChar() throws IOException{
		        //确定下一个token只有一个字符的时候再用
		        return next().charAt(0);
		    }
		    public int nextInt() throws IOException{
		        return Integer.parseInt(next());
		    }
		    public long nextLong() throws IOException{
		        return Long.parseLong(next());
		    }
		    public double nextDouble() throws IOException{
		        return Double.parseDouble(next());
		    }
		    public float nextFloat() throws IOException{
		        return Float.parseFloat(next());
		    }
		    public byte nextByte() throws IOException{
		        return Byte.parseByte(next());
		    }
		    public short nextShort() throws IOException{
		        return Short.parseShort(next());
		    }
		    public BigInteger nextBigInteger() throws IOException{
		        return new BigInteger(next());
		    }
		    public void println() throws IOException {
		        bw.newLine();
		    }
		    public void println(int[] arr) throws IOException{
		        for (int value : arr) {
		            bw.write(value + " ");
		        }
		        println();
		    }
		    public void println(int l, int r, int[] arr) throws IOException{
		        for (int i = l; i <= r; i ++) {
		            bw.write(arr[i] + " ");
		        }
		        println();
		    }
		    public void println(int a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(int a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(String a) throws IOException{
		        bw.write(a);
		        bw.newLine();
		    }
		    public void print(String a) throws IOException{
		        bw.write(a);
		    }
		    public void println(long a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(long a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(double a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(double a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void print(char a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(char a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		}
	}

poj3041 Asteroids

Here

解题思路

对于一个陨石 $(i,j)$ ，可以选择打第 $i$ 行或第 $j$ 列，一定只选其中一个
考虑二分图匹配
左集合为所有行，右集合为所有列，每个陨石看作行列的一条连边
所以打完陨石的最少次数，即选择最少的点实现对所有边覆盖
即求最小点覆盖，也就是最大匹配（最小点覆盖等于最大匹配）


import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.StringTokenizer;











//implements Runnable
public class Main{
	static long md=(long)998244353;
	static long Linf=Long.MAX_VALUE/2;
	static int inf=Integer.MAX_VALUE/2;
	static int N=501;
	static int n=0;
	static int k=0;
	


	static boolean[][] w=new boolean[N+1][N+1];
	static boolean[] visy=new boolean[N+1];
	static int[] link=new int[N+1];
	static boolean dfs(int x) {
		for(int i=1;i<=n;++i) {

			if(!visy[i]&&w[x][i]) {
				visy[i]=true;
				if(link[i]==0||dfs(link[i])) {
					link[i]=x;
					return true;
				}
			}
		}
		return false;
	}
	static void solve() throws Exception{
		AReader input=new AReader();
	    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));	
	    n=input.nextInt();
	    k=input.nextInt();
	    
	    for(int i=1;i<=k;++i) {
	    	int x=input.nextInt();
	    	int y=input.nextInt();
	    	w[x][y]=true;
	    }
	    int sum=0;
	    for(int i=1;i<=n;++i) {
	    	Arrays.fill(visy, false);
	    	if(dfs(i))sum++;
	    }
	    
	    out.print(sum);
 	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
		solve();
	}
//	public static final void main(String[] args) throws Exception {
//		  new Thread(null, new Main(), "线程名字", 1 << 27).start();
//	}
//		@Override
//		public void run() {
//			try {
//				//原本main函数的内容
//				solve();
//
//			} catch (Exception e) {
//			}
//		}
		static
		class AReader{ 
		    BufferedReader bf;
		    StringTokenizer st;
		    BufferedWriter bw;

		    public AReader(){
		        bf=new BufferedReader(new InputStreamReader(System.in));
		        st=new StringTokenizer("");
		        bw=new BufferedWriter(new OutputStreamWriter(System.out));
		    }
		    public String nextLine() throws IOException{
		        return bf.readLine();
		    }
		    public String next() throws IOException{
		        while(!st.hasMoreTokens()){
		            st=new StringTokenizer(bf.readLine());
		        }
		        return st.nextToken();
		    }
		    public char nextChar() throws IOException{
		        //确定下一个token只有一个字符的时候再用
		        return next().charAt(0);
		    }
		    public int nextInt() throws IOException{
		        return Integer.parseInt(next());
		    }
		    public long nextLong() throws IOException{
		        return Long.parseLong(next());
		    }
		    public double nextDouble() throws IOException{
		        return Double.parseDouble(next());
		    }
		    public float nextFloat() throws IOException{
		        return Float.parseFloat(next());
		    }
		    public byte nextByte() throws IOException{
		        return Byte.parseByte(next());
		    }
		    public short nextShort() throws IOException{
		        return Short.parseShort(next());
		    }
		    public BigInteger nextBigInteger() throws IOException{
		        return new BigInteger(next());
		    }
		    public void println() throws IOException {
		        bw.newLine();
		    }
		    public void println(int[] arr) throws IOException{
		        for (int value : arr) {
		            bw.write(value + " ");
		        }
		        println();
		    }
		    public void println(int l, int r, int[] arr) throws IOException{
		        for (int i = l; i <= r; i ++) {
		            bw.write(arr[i] + " ");
		        }
		        println();
		    }
		    public void println(int a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(int a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(String a) throws IOException{
		        bw.write(a);
		        bw.newLine();
		    }
		    public void print(String a) throws IOException{
		        bw.write(a);
		    }
		    public void println(long a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(long a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(double a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		    public void print(double a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void print(char a) throws IOException{
		        bw.write(String.valueOf(a));
		    }
		    public void println(char a) throws IOException{
		        bw.write(String.valueOf(a));
		        bw.newLine();
		    }
		}
	}