【HDU】3861 The King’s Problem 强连通缩点+有向图最小路径覆盖

2024-09-05 15:32

本文主要是介绍【HDU】3861 The King’s Problem 强连通缩点+有向图最小路径覆盖,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门:【HDU】3861 The King’s Problem


题目分析:首先强连通缩点,因为形成一个环的王国肯定在一条路径中,这样才能保证拆的少。

然后缩点后就是DAG图了,由于题目要求的是最小路径覆盖,那么二分匹配即可。


代码如下:


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
using namespace std ;#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )const int MAXN = 5005 ;
const int MAXE = 100005 ;
const int MAXQ = 1000005 ;
const int INF = 0x3f3f3f3f ;struct Edge {int v , n ;Edge () {}Edge ( int v , int n ) : v ( v ) , n ( n ) {}
} ;struct CC {Edge E[MAXE] ;int H[MAXN] , cntE ;int low[MAXN] , dfn[MAXN] , dfs_clock ;int S[MAXN] , top ;int scc[MAXN] , scc_cnt ;int n , m ;void init () {cntE = dfs_clock = scc_cnt = top = 0 ;CLR ( H , -1 ) ;CLR ( scc , 0 ) ;CLR ( dfn , 0 ) ;}void addedge ( int u , int v ) {E[cntE] = Edge ( v , H[u] ) ;H[u] = cntE ++ ;}void Tarjan ( int u ) {low[u] = dfn[u] = ++ dfs_clock ;S[top ++] = u ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( !dfn[v] ) {Tarjan ( v ) ;low[u] = min ( low[u] , low[v] ) ;}else if ( !scc[v] )low[u] = min ( low[u] , dfn[v] ) ;}if ( low[u] == dfn[u] ) {++ scc_cnt ;while ( 1 ) {int v = S[-- top] ;scc[v] = scc_cnt ;if ( v == u )break ;}}}void input () {int u , v ;scanf ( "%d%d" , &n , &m ) ;REP ( i , m ) {scanf ( "%d%d" , &u , &v ) ;addedge ( u , v ) ;}}void find_scc () {REPF ( i , 1 , n )if ( !dfn[i] )Tarjan ( i ) ;}void solve () {init () ;input () ;find_scc () ;}
} c ;struct Match {Edge E[MAXE] ;int H[MAXN] , cntE ;bool vis[MAXN] ;int Lx[MAXN] , Ly[MAXN] ;int dx[MAXN] , dy[MAXN] ;int Q[MAXQ] , head , tail ;int dis ;int n ;void init () {cntE = 0 ;CLR ( H , -1 ) ;}void addedge ( int u , int v ) {E[cntE] = Edge ( v , H[u] ) ;H[u] = cntE ++ ;}int Hopcroft_Karp () {CLR ( dx , -1 ) ;CLR ( dy , -1 ) ;head = tail = 0 ;dis = INF ;REPF ( i , 1 , n )if ( Lx[i] == -1 ) {Q[tail ++] = i ;dx[i] = 0 ;}while ( head != tail ) {int u = Q[head ++] ;if ( dx[u] >= dis )continue ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( dy[v] == -1 ) {dy[v] = dx[u] + 1 ;if ( Ly[v] == -1 )dis = dy[v] ;else {dx[Ly[v]] = dy[v] + 1 ;Q[tail ++] = Ly[v] ;}}}}return dis != INF ;}int find ( int u ) {for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( dy[v] == dx[u] + 1 && !vis[v] ) {vis[v] = 1 ;if ( ~Ly[v] && dy[v] == dis )continue ;if ( Ly[v] == -1 || find ( Ly[v] ) ) {Lx[u] = v ;Ly[v] = u ;return 1 ;}}}return 0 ;}int match () {int ans = 0 ;CLR ( Lx , -1 ) ;CLR ( Ly , -1 ) ;while ( Hopcroft_Karp () ) {CLR ( vis , 0 ) ;REPF ( i , 1 , n )if ( Lx[i] == -1 )ans += find ( i ) ;}return ans ;}void solve () {init () ;n = c.scc_cnt ;REPF ( u , 1 , c.n )for ( int i = c.H[u] ; ~i ; i = c.E[i].n ) {int v = c.E[i].v ;if ( c.scc[u] != c.scc[v] )addedge ( c.scc[u] , c.scc[v] ) ;}int ans = match () ;printf ( "%d\n" , n - ans ) ;}
} e ;int main () {int T ;scanf ( "%d" , &T ) ;while ( T -- ) {c.solve () ;e.solve () ;}return 0 ;
}


这篇关于【HDU】3861 The King’s Problem 强连通缩点+有向图最小路径覆盖的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139354

相关文章

SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志

《SpringBoot项目配置logback-spring.xml屏蔽特定路径的日志》在SpringBoot项目中,使用logback-spring.xml配置屏蔽特定路径的日志有两种常用方式,文中的... 目录方案一:基础配置(直接关闭目标路径日志)方案二:结合 Spring Profile 按环境屏蔽关

VSCode设置python SDK路径的实现步骤

《VSCode设置pythonSDK路径的实现步骤》本文主要介绍了VSCode设置pythonSDK路径的实现步骤,包括命令面板切换、settings.json配置、环境变量及虚拟环境处理,具有一定... 目录一、通过命令面板快速切换(推荐方法)二、通过 settings.json 配置(项目级/全局)三、

使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)

《使用Python和Matplotlib实现可视化字体轮廓(从路径数据到矢量图形)》字体设计和矢量图形处理是编程中一个有趣且实用的领域,通过Python的matplotlib库,我们可以轻松将字体轮廓... 目录背景知识字体轮廓的表示实现步骤1. 安装依赖库2. 准备数据3. 解析路径指令4. 绘制图形关键

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

Python如何调用指定路径的模块

《Python如何调用指定路径的模块》要在Python中调用指定路径的模块,可以使用sys.path.append,importlib.util.spec_from_file_location和exe... 目录一、sys.path.append() 方法1. 方法简介2. 使用示例3. 注意事项二、imp

使用Python实现矢量路径的压缩、解压与可视化

《使用Python实现矢量路径的压缩、解压与可视化》在图形设计和Web开发中,矢量路径数据的高效存储与传输至关重要,本文将通过一个Python示例,展示如何将复杂的矢量路径命令序列压缩为JSON格式,... 目录引言核心功能概述1. 路径命令解析2. 路径数据压缩3. 路径数据解压4. 可视化代码实现详解1

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使