CoolGuang!

图论

atcoder(4) kuangbin刷题记录(9) Task In College(1) 二分查找(5) 位运算(2) 动态规划(10) 博弈论(1) 备忘录(2) 大模拟(7) 字符串算法(3) 思维锻炼(14) 搜索(9) 数据结构(10) 数论(6) 暴力与随机数(3) 未归档(8) 矩阵练习(6) 组合数学(3) 计算几何(1) 计算机知识/辅助工具(1) 贪心算法(4) 路漫漫其修远兮(2) 题解(27)

/ 注册

全部文章 / 图论（共27篇）

Codeforce 1213G Path query 并查集

You are given a weighted tree consisting of nn vertices. Recall that a tree is a connected graph without cycles. Vertices uiui and vivi are connected ...

2020-01-13

0 644

CF1263D Secret Passwords 思维并查集

首先明确可能今晚这CF不适合图论选手，我应该倒着做的这个题没时间了...赛后wa了两发过了。真是午夜掉分场首先题意很明确了，两个字符串有相同字母，那么这两个字符串等效，注意！等效是可以传递的。题目思路：首先并查集绝对可以想得到，但是并查集怎么维护需要想一想。想最少的字符串，绝对找...

2020-01-13

0 568

2019ICPC南京现场赛 C-digit path 拓扑dp

说来惭愧，A题卡了4个小时我都不信，都最后铜也没拿上。。题意：找长度大于等于4的严格递增差1 的能在扩增的路线有多少条。题目思路：严格递增差一，很容易想到，有向无环图(DAG) 我们在DAG上进行拓扑DP就可以乐，因为拓扑满足无后效性所以，我们直接找出状态转移方程：...

2020-01-13

0 437

Codeforces Round #605 (Div. 3) E - Nearest Opposite Parity

题意：一个序列 i 可以移动到 i+ 与 i- 若是奇数，则终点为是偶数若是偶数，则终点为是奇数每个点最少需要多少步到达终点，到达不了输出-1 题解：思路的话，首先了解一下这个思路：每个点建立最多两条边 [i,i+] [i,i-] 不一定可以建成功要判断...

2020-01-13

0 615

Codeforces Round #609 (Div. 2) C Long Beautiful Integer 思维

题目大意：给一个字符串s，要求你构造一个字符串t，使得t>=s, 并且. 题目思路：构造的字符串可以看成，前k个字符循环构造而成。所以对前k个组成的数字进行+1即可，特判进位0。或者前k个数字不变，判断一下即可。很明显..思维题，AC： #include <bi...

2020-01-13

0 481

2019NOI 多校联合蓝精灵的请求二分图匹配分组背包

好久没有动CSDN了，还好吗老友~ 假期开始，博客也要跟进了~ 蓝精灵的请求题目大意：在山的那边海的那边住着n个蓝精灵，这n个蓝精灵之间有m对好友关系，现在蓝精灵们想要玩一个团队竞技游戏，需...

2020-01-13

0 0

图论定理整理及模板整理

定理整理：关于二分图： (1) 二分图的最小路径覆盖 1.最小不相交路径覆盖：Res==节点数-最大匹配数 2.最小可相交路径覆盖：首先floyd算法跑出所有可以到达的点，之后Res==节点数-最大匹配数 (2)二分图的最小顶点覆盖：定义：若选择一个点说明选择与它相连的所有边，最...

2020-01-13

0 532