最小割求解最大权闭合子图
定义有一个有向图，每一个点都有一个权值（可以为正或负或0），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。 如下图： 能选的子图有Ø,{4},{3,4},{2,4},{1,2,3,4},它们的权值分别为0,-1,5,-6,4. 所以最大权闭合子图为{3,4}，
...
操作系统三大经典同步问题
用专业术语来说, 进程是程序的一次动态执行.说简单点, 就是进程是系统中的某个任务.操作系统中有多个任务需要执行, 那么怎样执行才能使它们同步呢? 即如何让任务并发执行互不影响呢? 这就引出了进程同步中的经典问题: 生产者消费者问题, 哲学家进餐问题, 读写问题
生产者-消费者问题有一群生产者进程在
...
强连通图经典算法——Tarjan算法
Tarjan 算法
一.算法简介
Tarjan 算法一种由Robert Tarjan提出的求解有向图强连通分量的算法，它能做到线性时间的复杂度。
我们定义：
如果两个顶点可以相互通达，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有
...
NAIPC2016-F.Mountain Scenes
1000ms
262144K
An artist begins with a roll of ribbon, one inch wide. She clips it into pieces of various integral lengths, then aligns them with th
...
分时最短路+次小生成树+最小费用最大流题解
问题 A: 高速时间限制: 1 Sec 内存限制: 128 MB提交: 15 解决: 4[提交][状态][讨论版][命题人:qianyouyou]
题目描述教练开车去东北，因为比赛地点在东北。共有 n 座城，已知教练在 s 城，比赛地点在 t 城，n 座城之间共有 m 条高速，每条高速连接两座城
...
利用容斥原理求解范围内互素数对数例题
GCDGiven 5 integers: a, b, c, d, k, you’re to find x in a…b, y in c…d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Sinc
...
[转]容斥原理的三种运用方式
在计数时，必须注意无一重复，无一遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 集合相交通常情况为奇
...
[转]求解逆元的3种方法
简述逆元逆元(Inverse element)就是在mod意义下，不能直接除以一个数，而要乘以它的逆元。 比如a∗b≡1(modp)a∗b≡1(modp)，那么a，b互为模n意义下的逆元，比如你要算x/a，就可以改成x*b%p
观察a∗b≡1(modp)a∗b≡1(modp),变形为a∗b+k∗p=
...
2018-ACM/ICPC北京网络赛D题 80 Days（非暴力0(n)解法）
描述80 Days is an interesting game based on Jules Verne’s science fiction “Around the World in Eighty Days”. In this game, you have to manage the limite
...