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

hdu2448 题目链接 题意：n个船n个港口，一个港口只能承接一个船，m个油田，给出n个船各自在哪个油田，然后给出m个油田之间的无相图，然后给出油田和港口之间的有向图。求n个船到达港口的最小距离之和。 思路：想到了用floyd先更新一下距离，然后KM.不过思维不够严谨，只更新了港口通过油田到达油田的距离，而没有更新油田通过油田到达油田的距离QAQ. 所以应该先更新油田通过油田到达油田的距离，然后再更新港口通过油田到达油田的距离。。。 哦，还有。。。不要把n个船所对应的港口作为下标。。而是转化成1..n，这样写KM里会比较好写。。。不然总得带着那个id[i]. /* …

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的时候统计每个点入队的次数，如果一个 …

1641: [Usaco2007 Nov]Cow Hurdles 奶牛跨栏 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 531 Solved: 344 [Submit][Status][Discuss] Description Farmer John 想让她的奶牛准备郡级跳跃比赛，贝茜和她的伙伴们正在练习跨栏。她们很累，所以她们想消耗最少的能量来跨栏。 显然，对于一头奶牛跳过几个矮栏是很容易的，但是高栏却很难。于是，奶牛们总是关心路径上最高的栏的高度。 奶牛的训练场中有 N (1 ≤ N ≤ 300) 个站台，分别标记为1..N。所有站台之间有M (1 ≤ M ≤ 25,000)条单向 …

1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路 Time Limit: 5 Sec Memory Limit: 64 MB Submit: 507 Solved: 345 [Submit][Status][Discuss] Description  农夫约翰正驾驶一条小艇在牛勒比海上航行．  海上有N(1≤N≤100)个岛屿，用1到N编号．约翰从1号小岛出发，最后到达N号小岛．一 张藏宝图上说，如果他的路程上经过的小岛依次出现了Ai，A2，…，AM(2≤M≤10000)这样的序列（不一定相邻），那他最终就能找到古老的宝藏． 但是，由于牛勒比海有海盗出没．约翰知道任意两个岛屿之 …

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 <= …

题目链接 题意：有一条n个节点的链，节点i和节点j的距离为abs(i-j) 现在新增加三条边，距离也都为1，然后给出m个询问，每组询问给出两个点s,t，问s,t之间的最短距离。 思路：比赛的时候没搞出来。 观察特点，对于大多数点来说，都是没有直接的改变，只是增加了三条边。总的思路是：之前s到t的距离为abs(s-t),通过枚举中间经过的特殊点，观察是否能使得距离减小。 /* *********************************************** Author :111qqz Created Time :2016年03月31日 星期四 17时18分34秒 File Name :code/hdu/5636.cpp …

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 …

http://codeforces.com/contest/500/problem/B 题意：给定一个1至n的数的一种排列。给定一个n*n的矩阵，a[i][j]==0代表pi,pj不可以交换，a[i][j]为1代表p[i],p[j]可以交换。 问字典序最小的排列。。 思路：把矩阵看成图的关系。。反正n很小。。跑一遍floyd..得到可以间接交换的点。。然后冒泡排序就好。。只有p[i]>p[j]并且a[i][j]的时候交换。 /* *********************************************** Author :111qqz Created Time :2015年12月05日 星期六 15时00 …