【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

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :