俄语网站开发,运营商推广5g技术,网站黑名单查询,wordpress page 单页Going Home
Here 解题思路
模板 二分图最优匹配#xff0c;前提是有完美匹配#xff08;即存在一一配对#xff09;左右集合分别有顶标#xff0c;当时#xff0c;为有效边#xff0c;即选中初始对于左集合每个点#xff0c;选择其连边中最优的#xff0c;然后对于每…Going Home
Here 解题思路
模板 二分图最优匹配前提是有完美匹配即存在一一配对左右集合分别有顶标当时为有效边即选中初始对于左集合每个点选择其连边中最优的然后对于每个点找其最优匹配若能在前面连好边的图中找到匹配则继续下一个点若不能考虑撤销边如何撤销对于这次找增广路左集合中的点找一条不在这条增广路上的边进行替换找到最小代价即对于这次找增广路访问到的左集合右集合重复进行直到实现该点找到增广路可以添入或不能进行替换无完美匹配对于该题求最小只用将距离变为负值最后结果在反回来每次找增广路前清空 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 LinfLong.MAX_VALUE/2;static int infInteger.MAX_VALUE/2;static int N200;staticclass Node{int x;int y;public Node(int u,int v) {xu;yv;}}static int[][] wnew int[N1][N1];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 mm0;static int hh0;static int[] lxnew int[N1];static int[] lynew int[N1];static int[] linknew int[N1];static boolean[] visxnew boolean[N1];static boolean[] visynew boolean[N1];static Node[] mennew Node[N1];static Node[] homenew Node[N1];static boolean dfs(int x) {visx[x]true;for(int i1;ihh;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 inputnew AReader();PrintWriter out new PrintWriter(new OutputStreamWriter(System.out)); while(true) {int ninput.nextInt();int minput.nextInt();if(n0m0)break;mm0;hh0;Arrays.fill(link, 0);for(int i1;in;i) {String string input.next();char[] mpstring.toCharArray();for(int j1;jmp.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 i1;imm;i){for(int j1;jhh;j) {getw(men[i], home[j], i, j);}}for(int i1;imm;i) {lx[i]-inf;for(int j1;jhh;j) {ly[j]0;lx[i]Math.max(lx[i], w[i][j]);}}boolean oktrue;for(int i1;imm;i) {while(true) {//对于当前点i找个匹配,一直试Arrays.fill(visx, false);Arrays.fill(visy, false);int disinf;if(dfs(i))break;//直接不能找到//考虑改边for(int j1;jmm;j) {if(!visx[j]) continue;for(int k1;khh;k) {if(visy[k])continue;disMath.min(dis, (lx[j]ly[k])-w[j][k]);}}if(disinf) {okfalse;break;}for(int j1;jmm;j)if(visx[j])lx[j]-dis;for(int j1;jhh;j)if(visy[j])ly[j]dis;}if(!ok)break;}int sum0;if(ok) {for(int i1;ihh;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) {
// }
// }staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bfnew BufferedReader(new InputStreamReader(System.in));stnew StringTokenizer();bwnew BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){stnew 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 解题思路
对于一个陨石可以选择打第行或第列一定只选其中一个考虑二分图匹配左集合为所有行右集合为所有列每个陨石看作行列的一条连边所以打完陨石的最少次数即选择最少的点实现对所有边覆盖即求最小点覆盖也就是最大匹配最小点覆盖等于最大匹配 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 LinfLong.MAX_VALUE/2;static int infInteger.MAX_VALUE/2;static int N501;static int n0;static int k0;static boolean[][] wnew boolean[N1][N1];static boolean[] visynew boolean[N1];static int[] linknew int[N1];static boolean dfs(int x) {for(int i1;in;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 inputnew AReader();PrintWriter out new PrintWriter(new OutputStreamWriter(System.out)); ninput.nextInt();kinput.nextInt();for(int i1;ik;i) {int xinput.nextInt();int yinput.nextInt();w[x][y]true;}int sum0;for(int i1;in;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) {
// }
// }staticclass AReader{ BufferedReader bf;StringTokenizer st;BufferedWriter bw;public AReader(){bfnew BufferedReader(new InputStreamReader(System.in));stnew StringTokenizer();bwnew BufferedWriter(new OutputStreamWriter(System.out));}public String nextLine() throws IOException{return bf.readLine();}public String next() throws IOException{while(!st.hasMoreTokens()){stnew 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();}}}
