青烟绕指柔

图论

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

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

Codeforces - E. Tourism

E. Tourism time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Alex decided to go on a touristi...

2019-12-27

0 453

带树开花 - 带花树

带花树主要用来找一般图的最大匹配。例题：带花树例题如果是二分图，我们可以很简单的用匈牙利或者网络流等等方法找出来最大匹配。但是如果不是二分图呢？（有奇环）我们就需要用到带花树了。主要步骤：首先，奇环中有2k+1个点，所以最多有k组匹配。这就是说，有一个点没有匹配，即这个点...

2019-12-27

0 380

K Subsequence

K Subsequence Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 3577 Accepted Submission(s): 898 ...

2019-12-27

0 420

[COCI2006-2007#1] Bond

题意翻译有n 个人去执行n 个任务，每个人执行每个任务有不同的成功率，每个人只能执行一个任务，求所有任务都执行的总的成功率。输入第一行，一个整数n （1≤n≤20 ），表示人数兼任务数。接下来n 行每行n 个数，第i 行第j个数表示第i 个人去执行第j 个任务的成功率（这是一个百分数，在0 到...

2019-12-27

0 603

Link_Cut_Tree

LCT就是动态树的一种，但是相比Top_Tree来说，处理子树能力不足（但是简单）。 LCT利用轻重路径的划分，也就是实边和虚边来实现边的删除和合并。现在来说说LCT的几个重要操作：（默认会splay） access(x) : 让x连到根上面，也就是让根到x的边全部变为实边。所以我...

2019-12-27

0 367

树上长度为k的路径

题目描述给定一棵有n个点的树询问树上距离为k的点对是否存在。输入格式 n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径接下来m行每行询问一个K 输出格式对于每个K每行输出一个答案，存在输出“AYE”,否则输出”NAY”(不包含引号) 输入输出样例输入 #1复制 ...

2019-12-27

0 751

bzoj 2049 [Sdoi2008]Cave 洞穴勘测

2049: [Sdoi2008]Cave 洞穴勘测 Time Limit: 10 Sec Memory Limit: 259 MB Submit: 11970 Solved: 5988 [Submit][Status][Discuss] Description 辉辉热衷于洞穴勘测。某天，他按照地图...

2019-12-27

0 329

bzoj 1180 [CROATIAN2009]OTOCI

1180: [CROATIAN2009]OTOCI Time Limit: 50 Sec Memory Limit: 128 MB Submit: 1463 Solved: 941 [Submit][Status][Discuss] Description 给出n个结点以及每个点初始时对应的权值w...

2019-12-27

0 391

[国家集训队]Tree II

题目链接：[国家集训队]Tree IIv LCT维护树上链加法和乘法。我们像线段树一样做一个加法标记，和一个乘法标记即可。转移和线段树一样的。因为保证边是合法的，所以我们link和cut时就不必判断了。 AC代码： #pragma GCC optimize(2) #includ...

2019-12-27

0 376

[国家集训队]聪聪可可

题目描述聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上...

2019-12-27

0 414