Description 为了防止口渴的食蚁兽进入他的农场，Farmer John决定在他的农场周围挖一条护城河。农场里一共有N(8<=N<=5,000)股泉水，并且，护城河总是笔直地连接在河道上的相邻的两股泉水。护城河必须能保护所有的泉水，也就是说，能包围所有的泉水。泉水一定在护城河的内部，或者恰好在河道上。当然，护城河构成一个封闭的环。 挖护城河是一项昂贵的工程，于是，节约的FJ希望护城河的

[Usaco2006 Dec]Wormholes 虫洞 时间限制: 1 Sec 内存限制: 128 MB 题目描述 John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=20

[Usaco2006 Open]County Fair Events 参加节日庆祝 Description Farmer John has returned to the County Fair so he can attend the special events (concerts, rodeos, cooking shows, etc.). He wants to attend as m

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1654 题目大意 求图中包括点数大于1的强连通分量数 题解 模板测试 varw:array[0..70000,1..2]of longint;low,dfn,p,t:array[0..10005]of longint;i,j,k:longint;n,m,len,a,b,tmp,an

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1651 题目大意 给出奶牛运动的时间段,询问同一时间最多的奶牛数 题解 线段树或差分序列 线段树 varx:array[0..3000000,1..4]of longint;i,j,k:longint;n,a,b,m:longint;function max(a,b:longi

看到第一眼就发觉是壮压DP 然后就三进制枚举子集吧。 这题真是壮压入门好题。。。 对于dp[i][j] 表示第i行，j状态下前i行的分配方案数。 那么dp[i][j]肯定是从i-1行转过来的 那么由于不能挨着放，那么我们肯定是枚举i - 1行状态时不能包含j的任何一位。 那么只要令k = ((1 << n) - 1) ^ j，k中肯定就不包含j的位了 是这样枚举k的子集 in