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

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

 

 

 

 

 

 

 

 

hdu 2448 Mining Station on the Sea (floyd+KM)

hdu2448 题目链接

题意:n个船n个港口,一个港口只能承接一个船,m个油田,给出n个船各自在哪个油田,然后给出m个油田之间的无相图,然后给出油田和港口之间的有向图。求n个船到达港口的最小距离之和。

思路:想到了用floyd先更新一下距离,然后KM.不过思维不够严谨,只更新了港口通过油田到达油田的距离,而没有更新油田通过油田到达油田的距离QAQ.

所以应该先更新油田通过油田到达油田的距离,然后再更新港口通过油田到达油田的距离。。。

哦,还有。。。不要把n个船所对应的港口作为下标。。而是转化成1..n,这样写KM里会比较好写。。。不然总得带着那个id[i].

 

选区_074

 

 

 

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 1641: [Usaco2007 Nov]Cow Hurdles 奶牛跨栏 (floyd)

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)条单向路径,第i条路经是从站台Si开始,到站台Ei,其中最高的栏的高度为Hi (1 ≤ Hi ≤ 1,000,000)。无论如何跑,奶牛们都要跨栏。 奶牛们有 T (1 ≤ T ≤ 40,000) 个训练任务要完成。第 i 个任务包含两个数字 Ai 和 Bi (1 ≤ Ai ≤ N; 1 ≤ Bi ≤ N),表示奶牛必须从站台Ai跑到站台Bi,可以路过别的站台。奶牛们想找一条路径从站台Ai到站台Bi,使路径上最高的栏的高度最小。 你的任务就是写一个程序,计算出路径上最高的栏的高度的最小值。

Input

行 1: 两个整数 N, M, T 行

2..M+1: 行 i+1 包含三个整数 Si , Ei , Hi 行 M+2..M+T+1: 行 i+M+1 包含两个整数,表示任务i的起始站台和目标站台: Ai , Bi

Output

行 1..T: 行 i 为一个整数,表示任务i路径上最高的栏的高度的最小值。如果无法到达,输出 -1。

Sample Input

5 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1

Sample Output

4
8
-1

HINT

Source

 

思路:floyd.

坑成傻逼。

BZOJ用CIN/COUT会迷之RE!!!

BZOJ用CIN/COUT会迷之RE!!!

BZOJ用CIN/COUT会迷之RE!!!

 

 

 

BZOJ 1624: [Usaco2008 Open] Clear And Present Danger 寻宝之路 (Floyd)

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)这样的序列(不一定相邻),那他最终就能找到古老的宝藏.  但是,由于牛勒比海有海盗出没.约翰知道任意两个岛屿之间的航线上海盗出没的概率,他用一个危险指数Dij(0≤Dij≤100000)来描述.他希望他的寻宝活动经过的航线危险指数之和最小.那么,在找到宝藏的前提下,这个最小的危险指数是多少呢?

Input

    第1行输入N和M,之后M行一行一个整数表示A序列,之后输入一个NxN的方阵,表示两两岛屿之间航线的危险指数.数据保证Dij=Dji,Dii=0.

Output

    最小的危险指数和.

Sample Input

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

INPUT DETAILS:

There are 3 islands and the treasure map requires Farmer John to
visit a sequence of 4 islands in order: island 1, island 2, island
1 again, and finally island 3. The danger ratings of the paths are
given: the paths (1, 2); (2, 3); (3, 1) and the reverse paths have
danger ratings of 5, 2, and 1, respectively.

Sample Output

7

OUTPUT DETAILS:

He can get the treasure with a total danger of 7 by traveling in
the sequence of islands 1, 3, 2, 3, 1, and 3. The cow map’s requirement
(1, 2, 1, and 3) is satisfied by this route. We avoid the path
between islands 1 and 2 because it has a large danger rating.

HINT

Source

 

思路:可以把危险指数看成距离,于是floyd一下就好咯

 

 

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解题报告

bc #74 div1 1001 || hdu 5636 Shortest Path (floyd?)

题目链接
题意:有一条n个节点的链,节点i和节点j的距离为abs(i-j)
现在新增加三条边,距离也都为1,然后给出m个询问,每组询问给出两个点s,t,问s,t之间的最短距离。
思路:比赛的时候没搞出来。 观察特点,对于大多数点来说,都是没有直接的改变,只是增加了三条边。总的思路是:之前s到t的距离为abs(s-t),通过枚举中间经过的特殊点,观察是否能使得距离减小。

 

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个点是否和他有关系。

 

 

codeforces 500 B. New Year Permutation

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]的时候交换。