首页
编程日记
ChatGpt专题
LINUX学习
Java学习
前端教程
单片机
网络安全
保研
scipy
Shell脚本
zabbix
opencv
AOE网
USB
ROBOGUIDE
损失函数
2022
在线聊天系统
VECTOR工具
java-zookeeper
异步
symbol
qt布局管理器
素数
tee
安杰思
tarjan
2024/4/12 2:07:52
bzoj 2208: [Jsoi2010]连通数
Description Input 输入数据第一行是图顶点的数量,一个正整数N。 接下来N行,每行N个字符。第i行第j列的1表示顶点i到j有边,0则表示无边。 Output 输出一行一个整数,表示该图的连通数。 Sample Input 3 010 001 100 Sample Outp…
阅读更多...
【题解】P3119 [USACO15JAN] Grass Cownoisseur
题意 传送门 题意很简单,给定一张有向图,允许选择在一条边上反向行走一次,求从1出发,且最终回到1,最多能遍历到的点数。 Solution 一道综合性的图论好题。 首先想到,对于一个强连通分量内的点…
阅读更多...
有向图的强连通性(java)
Kosaraju算法 一句话理解Kosaraju算法:按从终点向起点遍历的顺序遍历有向图,如果能遇到起点,那么就说明该两点之间是强连接关系。 Tarjan算法 package graph.digraph;import java.io.File; import java.io.FileNotFoundException; import …
阅读更多...
算法随笔:强连通分量
概念和性质: 强连通:在有向图G中,如果两个点u和v是互相可达的,即从u出发可以到达v,从v出发也可以到达u,则成u和v是强连通的。 强连通分量:如果一个有向图G不是强连通图,那么可以把它…
阅读更多...
poj2942:Knights of the Round Table(Tarjan)
传送门 题意: 亚瑟王要在圆桌上召开骑士会议,为了不引发骑士之间的冲突,并且能够让会议的议题有令人满意的结果,每次开会前都必须对出席会议的骑士有如下要求: 1、 相互憎恨的两个骑士不能坐在直接相邻的2个位置&am…
阅读更多...
蓝桥杯 2017 决赛 发现环 (求环内的点)
历届试题 发现环 时间限制:1.0s 内存限制:256.0MB问题描述小明的实验室有N台电脑,编号1~N。原本这N台电脑之间有N-1条数据链接相连,恰好构成一个树形网络。在树形网络上,任意两台电脑之间有唯一的路径相连。不过在最…
阅读更多...
C++学习笔记:图论——缩点详解
引言 缩点,哲学的东西,你必须拥有。。。 缩点 个人认为就是把一堆强连通的点( 即强连通分量 ),认作为一个点 强连通分量就是这里面的点可以相互到达(算是个环) 详解 一个有向图如下 可以看出有强连通分量 { 1 , 2 …
阅读更多...
C++学习笔记:有向图的强连通分量
强连通图分量 首先得知道这是个什么玩意儿,对于一个如下的有向图 在这个有向图G中,如果有两个点可以相互到达,则两点为强连通,若图中每个点都可以相互到达,则图G为强连通图 1. 一个有向图是强连通的,而且仅…
阅读更多...
间谍网络(C++,强连通分量,缩点)
题目描述 由于外国间谍的大量渗入,国家安全正处于高度的危机之中。如果 A 间谍手中掌握着关于 B 间谍的犯罪证据,则称 A 可以揭发 B。有些间谍收受贿赂,只要给他们一定数量的美元,他们就愿意交出手中掌握的全部情报。所以&#x…
阅读更多...
poj3678:Katu Puzzle(2-SAT)
传送门 题意 有一个大小为N的集合{x1,x2..xn},xi0或1,现在给出它们之间的一些逻辑运算的结果(比如x1 and x21),逻辑运算有AND OR XOR三种,问是否存在一种满足所有条件的取值方案。 题解:2-SAT 这道题真是把2-SAT思想诠释得淋漓…
阅读更多...
POJ 1986 Distance Queries Tarjan算法求最近公共祖先+前向星
第一次尝试自己写博客,如果有什么不好的地方还请大家多多批评指正~传送门:POJ 1986题目大意: John是一个农场主,他的牛都懒散惯了,所以拒绝按照John所选的路走。John就想找一条最短的路。本题输入前半部分与“导航噩梦…
阅读更多...
poj1236:Network of School(Tarjan)
Description 一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意如果 B 在 A 学校的分发列表中,那么 A 不必也在 B 学校的列表中。 你要写一个程序计算,…
阅读更多...
Tarjan求图的割点、桥与双连通分量
关于Tarjan的部分知识:poj1236:Network of School(Tarjan) 图的割点桥与双连通分量定义点连通度与边连通度双连通图割点与桥双连通分量分支 Tarjan算法求双连通分量例题 图的割点、桥与双连通分量 定义 点连通度与边连通度: …
阅读更多...
Petrozavodsk Winter Training Camp 2018: Carnegie Mellon U Contest A. Mines
题目大意: 给你n个点,分别位于pi。每个点有个爆炸范围ri和代价ci,花费ci可以引爆某个点,并且pi-ri到piri范围内的点都会被引爆。q个询问,每次修改一个点的ci,每次输出引爆所有店的最小代价。 题解…
阅读更多...
poj2749:Building roads(2-SAT)
传送门 题意 有N个农场,其中A对相互讨厌,不能碰面;B对相互喜欢,必须碰面。给定两个中转站S1和S2、各个农场的坐标,让每个农场连接到其中一个中转站。求最小化任意两个农场通过中转站的最大距离,若无法实现…
阅读更多...
bzoj 1051: [HAOI2006]受欢迎的牛
Description 每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少…
阅读更多...
[APIO2018]铁人两项
Description 给出一张n个点,m条边的简单无向图,求有多个三元组(s,f,t),满足两两互不相等且存在至少一条从s出发经过f到t的不经过重复点的路径。 n<1e5,m<2e5 Solution 考场都去做A了没仔细想C,以为很麻烦 其实把圆方树…
阅读更多...
bzoj 1529: [POI2005]ska Piggy banks
Description Byteazar 有 N 个小猪存钱罐. 每个存钱罐只能用钥匙打开或者砸开. Byteazar 已经把每个存钱罐的钥匙放到了某些存钱罐里. Byteazar 现在想买一台汽车于是要把所有的钱都取出来. 他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.Input 第一行一个整数…
阅读更多...
C++学习笔记:Tarjan算法剖析——求 强连通分量,割点,割边,点双连通分量,边双连通分量 的详解
Tarjan算法详解 目录 1.Tarjan算法求强连通分量 2. Tarjan算法求割点 3. Tarjan算法求点双连通分量 4. Tarjan算法求割边 5. Tarjan算法求边双连通分量 1.Tarjan算法求强连通分量 了解一下 强连通分量 对于一个有向图的DFS的搜索树(i 可以到 j,j…
阅读更多...
模拟赛 轰炸
题目大意 有 nnn 座城市,城市之间建立了mmm 条有向的地下通道。 你需要发起若干轮轰炸,每轮可以轰炸任意多个城市。但每次轰炸的城市中,不能存在两个不同的城市 iii,jjj 满足可以通过地道从城市 iii 到达城市 jjj。 你需要求出…
阅读更多...
Loj10103「一本通 3.6 练习 4」电力
题目传送门 题意 求一个图删除一个点之后,联通块最多有多少。 思路 很显然对于在有割点的情况下,要删除割点,而删除割点后增加的连通块个数可以这样计算: 设num[i]表示第i个点被删除后增加的连通块个数。 当前点x为…
阅读更多...
比赛
题目描述 经过千辛万苦,orez和mjw终于成功逃离了LG的追杀,来到了XD的地盘。XD为了迎接两位影星的到来,决定举行一场友谊比赛来迎接他们。这次比赛将这样进:每次orez和mjw都可以从参赛者中选择两个人进行比赛,败者将被…
阅读更多...
[CF 732F]Tourist Reform
Description 给出一张n个点,m条边的无向联通图,现在你要给每条边一个方向,设f(x)表示x所能到达的点的数量,你需要使得最小的f(x)最大。 求一种方案。 n,m<4*10^5 Solution 这道题一点都不像F题(毕竟div.2&…
阅读更多...