为什么不问问神奇海螺呢

分类

2018暑假组队赛记录(1) ACM_心情(6) codeforces2018(7) DFS/BFS搜索(10) Linux-Ubuntu(1) python(1) STL(12) 二分搜索(9) 健身(2) 几何之凸包问题(10) 几何之半平面交(6) 几何之旋转卡壳(2) 几何之模拟退火(5) 几何之面积问题(9) 几何技巧(7) 几何问题非模板问题(5) 动态规划之基础DP(54) 动态规划之状态压缩(1) 图论之二分图(5) 图论之强联通SCC(5) 图论之网络流(8) 套题(2) 学习(10) 学习资料(28) 年月问题(3) 思维(47) 括号匹配(2) 数学之博弈(6) 数据结构之Manacher(2) 数据结构之单调队列(1) 数据结构之字典树(3) 数据结构之字符串匹配KMP(4) 数据结构之并查集(10) 数据结构之生成树(3) 数据结构之线段树/树状数组(11) 数据结构之莫队算法(1) 数论之Mobius莫比乌斯反演(6) 数论之Nim博弈及变形(2) 数论之伯努利数(1) 数论之佩尔方程(4) 数论之因数相关(1) 数论之数学期望(2) 数论之组合数学(8) 数论之质数相关(1) 数论之进制转换(1) 暴力题(14) 未归档(37) 构造题(3) 模拟(9) 模板集合(打印)(9) 玄学黑科技(1) 生活分享(2) 电影(2) 算法学习(18) 自然溢出(1) 规律(7) 读书(7) 读书笔记(7) 贪心(21) 随机or玄学(1) 高精度(1)

/ 注册

全部文章（共465篇）

关于二分图

1.二分图的判定: BFS,不能有奇数的环(引理) 2.二分图最大匹配(匈牙利算法,增广路) 3.二分图建模... 主要能看到把一个集合分成2个内部无边的集合.边可以是某种关系. 并且最大匹配数/最小覆盖点数.正好是题目要求的答案 4.多重匹配和带权最大匹配用网络流解决 5.二分图最小点覆...

2018-07-19

0 497

Machine Schedule HDU - 1150

Machine Schedule 题意:A,B两个机器,每个机器有M种模式a[M],b[M].现在有N个任务,每个任务需要a[i]或者b[i].每当机器转换一种机器模式,问至少转换多少次机器模式? 思路:对于a[i],b[i]连一条边.即求至少多少个点,能把整个二分图的边至少有一个端点覆盖.即二...

2018-07-19

0 663

車的放置[二分图最大匹配数]

車的放置题意:n*m的棋盘上有t个位置被禁止放置东西,问最多可以放置多少个"车" 思路:我们必须找到2个集合,每个集合内部没有边,每一条边的两个端点在两个集合.以行坐标为A集合,列坐标为B集合那么A,B内部均无边,且所有边的两个端点都在两个集合里一个端点只能属于一条...

2018-07-19

0 464

4949: 棋盘覆盖[二分图最大匹配]

4949: 棋盘覆盖题意:一个n*n的棋盘,现在有m个位置是禁止放东西的,问最多可以放多少个 1 * 2 的骨牌 , 输出结果思路:n*n地图上能放骨牌的所有方格中心点连边,我们可以发现,这些边可以构成一个二分图,在对角线关系的所有点都是一个集合,并且集合内部没有边.现在求二分图的最大匹配...

2018-07-18

0 682

4844: Noip2010 关押罪犯[BFS判二分图]

4844: Noip2010 关押罪犯题意:有n名罪犯,有m对关系a,b,c分别代表罪犯a和罪犯b有矛盾值c. 现在将这些囚犯放到2个监狱(集合),问最少的矛盾值会是多少思路:二分最少的矛盾值mid,如果边权<=mid不影响结果,对于>mid的所有边,看是否能形成一张二分图 ...

2018-07-18

0 480

E. We Need More Bosses【无向图强连通】

E. We Need More Bosses 题意: 求一个无向图缩点后,求直径长度注意无向图强连通和有向图强连通是有区别的，主要是无向图强连通不能回头，要求在tarjan算法里记录father #include<bits/stdc++.h> #define PI acos(-...

2018-07-17

0 439

D. Pave the Parallelepiped[组合数学+位运算判断集合包含关系]

D. Pave the Parallelepiped 题意:给定三个数A,B,C(1e5),这三个数分别选一个因数,a,b,c. 满足情况a<=b<=c,问有多少个满足的组合思路:将集合ABC这3个集合,划分成7个集合,暴力枚举三个数从7个中哪3个选.并利用几何编号的关系判断集合的包含...

2018-07-14

0 544

E. Anton and Tree[树的直径]

E. Anton and Tree 转化的题意: 一张黑白相间的树,一次操作可以把一片联通的白色顶点变成黑色,黑色变成白色.问至少需要多少次操作让图变成一种颜色思路: 树的直径为d 答案为 (d+1)/2 证明: 首先,至少为 (d+1)/2 , 现在需要证明这个答案能成立. 每次取中间的...

2018-07-11

0 448

E2. Median on Segments (General Case Edition)【思维】好题

E2. Median on Segments (General Case Edition) 题意：E1的强化版本。问中位数是m的区间有多少个思路：定义run(m)：中位数<=m的区间个数，则有式①：cnt[小于等于m的数] >= cnt[大于m的数] 。预处理一下，用数状数组维护。想...

2018-07-10

0 552

E1. Median on Segments (Permutations Edition)[如何判断无序中位数]

E1. Median on Segments (Permutations Edition) 题意:一个长为n的打乱的全排列,给定m,问包含m的区间中,有多少个区间的中位数是m 思路:假设m的位置为pos,先处理出[pos+1~n]中到达每个点的,比m大和比m小的差值. 假设一个区间可以,那么有大...

2018-07-10

0 657