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篇）

二分图匹配 Hopcroft-Carp (HK) 算法详解附例题

了解这个算法之前首先了解一个概念：增广路增广路：简单的说，是二分图匹配中的一条边，他总是从左边集合的一个点出发通过一条没有被匹配的边连接到右边集合，再从该点通过一条匹配过的边连接到右边集合。图1为正常的二分图图2为二分图的最大匹配图3 为二分图最大匹配中的增广路两...

2020-01-13

0 1389

2019 ICPC 徐州网络赛 B so easy 并查集+STL

题目大意：每次你可以使一个数失效，或者询问大于该数的第一个有效数是哪个数字。题目思路：考虑并查集，由于n与x太大，所以用map的并查集，undorered map不会超时否则普通map会t ac: #include<bits/stdc++.h> #define ll l...

2020-01-13

0 547

2019中石油秋季个人训练赛2 B 小说分层建图

问题 B: 小说时间限制: 1 Sec 内存限制: 128 MB 提交: 88 解决: 36 [提交] [状态] [命题人:admin] 题目描述由于小X是一位奆老，奆老总是忙得一刻也停不下来。他刚刚准备完食物，小X童年的挚友小S和小Z来找他帮忙了…… 小S和小Z十分喜欢看网络写...

2020-01-13

0 540

中石油专题&&洛谷 P1124 最短路计数图上dp

问题 M: 最短路计数时间限制: 1 Sec 内存限制: 128 MB 提交: 25 解决: 8 [提交] [状态] [命题人:admin] 题目描述给出一个N个顶点M条边的无向无权图，顶点编号为1～N。问从顶点1开始，到其他每个点的最短路有几条。输入第一行包含2个正整数...

2020-01-13

0 661

New Traffic System LightOJ - 1281 分层最短路+条件限制最短路

The country - Ajobdesh has a lot of problems in traffic system. As the Govt. is very clever (!), they made a plan to use only one way roads. Two citie...

2020-01-13

0 680

Prime Independen 素数拆分+二分图匹配+最大独立集

A set of integers is called prime independent if none of its member is a prime multiple of another member. An integer a is said to be a prime multiple...

2020-01-13

0 618

Not The Best 严格第二短路 A*第k短路或者次短路算法

Robin has moved to a small village and sometimes enjoys returning to visit one of his best friends. He does not want to get to his old home too quickl...

2020-01-13

0 513

Codefroce 653E Bear and Forgotten Tree 2 (补图的联通块)

判断补图的联通块及连通性模板:第10个补图联通块 A tree is a connected undirected graph consisting of n vertices and n - 1 edges. Vertices are numbered 1through n. Limak...

2020-01-13

0 714

POJ 2186 Popular Cows 强连通分量缩点处理

Online Judge Problem Set Authors Online Contests User Web BoardHome PageF.A.QsStatistical Charts ProblemsSubmit Problem...

2020-01-13

0 576

Codeforce1213 F G - Unstable String Sort 强连通分量+拓扑排序

Authors have come up with the string ss consisting of nn lowercase Latin letters. You are given two permutations of its indices (not necessary equal)...

2020-01-13

0 477