111qqz的小窝

老年咸鱼冲锋!

hdu 5036 Explosion||2014 北京区域赛网络赛 (概率+bitset优化的状态压缩+floyd传递闭包)

题目链接

题意:有n扇门,n种钥匙,一一对应。每扇门打开后可能得到k把钥匙(k可能为0)。一扇门还可以用一颗炸弹炸开。现在问要开所有门,使用炸弹的期望个数。

思路:状态压缩。用一个二进制串表示每扇门能打开的门的信息,对应的位上为1表示能打开,为0表示不能打开。

状态是可以传递的。。

如果第i扇门能打开门k,那么能打开第i扇门的第j扇门也可以打开门k。

状态压缩以及传递的过程可以很容易用bitset来维护,这才是bitset的正确打开姿势

相当于用floyd做了一个传递闭包。(floyd的有一层循环隐藏在了bitset中,复杂度没有改变,但是常数小)

最后对于期望的计算方法:统计能打开第i扇门的方案数计为cnt,这cnt的方案中,只有一种是用炸弹炸掉,因此用的炸弹数的期望数为1/cnt

由于期望的独立性,因此打开所有门所有的炸弹数的期望就是每个门的期望累加。

 

 

 

 

 

 

 

 

poj 2594 Treasure Exploration (DAG图最小路径覆盖变形,匈牙利算法+floyd求传递闭包)

poj 2594 题目链接

题意:一个DAG图,每个点有宝藏…可以降落任意个机器人到任意点…然后机器人可以沿着路径走,路过某个点的时候,可以取走该点的宝藏。问要取走所有宝藏,最少需要多少个机器人。

思路:乍一看。。很像DAG图的最小路径覆盖。。但是最小路径覆盖是要求每个点只能经过一次的。。而这道题路过某个点的时候,可以不取走宝藏。。以及题面里明确说了“you should notice that the roads of two different robots may contain some same point.

那是否还可以用最小路径覆盖做呢。。答案是可以的。。。

区别就在于一个点如果被一条路径使用过一次,还可不可以使用第二次。。。

如果我们按照传统的DAG图的最小路径覆盖考虑。。。如果一个点会被路径经过两次。。。那么我们不妨增加一个点。。。 进一步考虑。。。我们要的是尽可能覆盖所有点。。。如果这条路径前后的点不会因为这个点而中断,那么这个增设点是否存在,其实是无所谓的,只要改点前后的点连通性不受影响即可。 说到连通性,不禁想到floyd求传递闭包。

 

然后对于DAG图的最小路径覆盖问题。。。就可以用hungary算法求解。。。

ans = n – 最大匹配数。

这应该算作hungary的一个应用。

 

poj 1932 XYZZY (floyd传递闭包+spfa求最长路)

poj1932题目链接

题意:初始在点1,有100点能量,然后每个点有一个能量值【-100,100】,经过某个点会加上这个点的能量值,问能否找到一条到点n且的路线,且路径任何点的能量值一直为正。一共不超过100个点。

 

思路:像样例中是直接联通,一路上的能量值都大于0,这是有解的一种情况。另一种是存在一个正环,可能一次路过后面的能量值不够,但是我们可以走多次啊。

因为要求每一步的能量值都大于0,那么我们可以初始化d[]数组为0,然后用spfa求最长路(只需要把那个三角形等式换个方向即可)

如果可以直接联通,也就是d[n]>0,那么有解。

还有可能是存在一个环(判断环的方法是用一个数组在spfa的时候统计每个点入队的次数,如果一个点的入队次数大于n,那么就存在环,且这个点在环中

但是我们还要保证起点1和终点n是经过这个环的。

所以先跑一发floyd. 其实n才100也算给了提示吧,不用floyd的话没道理这么小的数据。。?

感觉这道题很棒,把spfa和floyd结合在了一起。

学到了判断环的方法,spfa求最长路的方法,复习了传递闭包。

 

 

 

 

BZOJ 1612: [Usaco2008 Jan]Cow Contest奶牛的比赛(floyd,传递闭包)

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; 1 <= B <= N; A != B) ,那么她们的对决中,编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名,于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果,希望你能根据这些信息,推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

Input

* 第1行: 2个用空格隔开的整数:N 和 M

* 第2..M+1行: 每行为2个用空格隔开的整数A、B,描述了参加某一轮比赛的奶 牛的编号,以及结果(编号为A,即为每行的第一个数的奶牛为 胜者)

Output

* 第1行: 输出1个整数,表示排名可以确定的奶牛的数目

Sample Input

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output

2

输出说明:

编号为2的奶牛输给了编号为1、3、4的奶牛,也就是说她的水平比这3头奶
牛都差。而编号为5的奶牛又输在了她的手下,也就是说,她的水平比编号为5的
奶牛强一些。于是,编号为2的奶牛的排名必然为第4,编号为5的奶牛的水平必
然最差。其他3头奶牛的排名仍无法确定。

题意:给出m场比赛结果,问能确定多少头奶牛的排名。
思路:容易联想到拓扑排序。。。然而并不对。。其实这题之前做过。。。能确定一头奶牛的条件是,知道它和其他n-1头奶牛的关系,被打败或者打败都可以…由于n才100,直接floyd,传递闭包。
同poj 3660

poj3660解题报告

poj 3660 Cow Contest (floyd,传递闭包)

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