题目链接 题意：有n扇门，n种钥匙，一一对应。每扇门打开后可能得到k把钥匙（k可能为0）。一扇门还可以用一颗炸弹炸开。现在问要开所有门，使用炸弹的期望个数。 思路：状态压缩。用一个二进制串表示每扇门能打开的门的信息，对应的位上为1表示能打开，为0表示不能打开。 状态是可以传递的。。 如果第i扇门能打开门k，那么能打开第i扇门的第j扇门也可以打开门k。 状态压缩以及传递的过程可以很容易用bitset来维护，这才是bitset的正确打开姿势 相当于用floyd做了一个传递闭包。(floyd的有一层循环隐藏在了bitset中，复杂度没有改变，但是常数小) 最后对于期望的计算方法：统计能打开第i扇门的方案数计为cnt,这cnt的方案中，只有 …

poj 2594 题目链接 题意：一个DAG图，每个点有宝藏...可以降落任意个机器人到任意点...然后机器人可以沿着路径走，路过某个点的时候，可以取走该点的宝藏。问要取走所有宝藏，最少需要多少个机器人。 思路：乍一看。。很像DAG图的最小路径覆盖。。但是最小路径覆盖是要求每个点只能经过一次的。。而这道题路过某个点的时候，可以不取走宝藏。。以及题面里明确说了“you should notice that the roads of two different robots may contain some same point. ” 那是否还可以用最小路径覆盖做呢。。答案是可以的。。。 区别就在于一个点如果被一条路径使用过一次，还可不 …

poj1932题目链接 题意：初始在点1，有100点能量，然后每个点有一个能量值【-100,100】，经过某个点会加上这个点的能量值，问能否找到一条到点n且的路线，且路径任何点的能量值一直为正。一共不超过100个点。 思路：像样例中是直接联通，一路上的能量值都大于0，这是有解的一种情况。另一种是存在一个正环，可能一次路过后面的能量值不够，但是我们可以走多次啊。 因为要求每一步的能量值都大于0，那么我们可以初始化d[]数组为0，然后用spfa求最长路（只需要把那个三角形等式换个方向即可） 如果可以直接联通，也就是d[n]>0，那么有解。 还有可能是存在一个环（判断环的方法是用一个数组在spfa的时候统计每个点入队的次数，如果一个 …

1612: [Usaco2008 Jan]Cow Contest奶牛的比赛 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 900 Solved: 597 [Submit][Status][Discuss] Description FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= …

http://poj.org/problem?id=3660 题意：给定n个奶牛，m个奶牛的关系，a,b表示a比b强...问能确定多少个奶牛的排名。 思路：最重要的一点是。。能确定奶牛i的排名的条件是。。知道奶牛i和其他n-1个奶牛的关系。。不管是能打败奶牛i也好。。会被奶牛i打败也好。。只要不是不确定就行。。所以我们跑一遍floyd做传递闭包。得到任何两个点之间的联系。然后对于每一个点。看其他n-1个点是否和他有关系。 /* *********************************************** Author :111qqz Created Time :2015年12月17日 星期四 21时31分05 …