图论练习5

🕗 发布于 2024-03-07 16:26 图论算法

Going Home

解题思路

$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();
    }
}
}

原文地址：https://blog.csdn.net/Xing_ke/article/details/136519252

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：蓝牙系列五：开源蓝牙协议BTStack框架代码阅读（1）
下一篇：python模块百科_操作系统接口_os【一】

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20

图论练习5

Going Home

解题思路

poj3041 Asteroids

解题思路

相关文章