Mrhanice

图论

codeforces(2) DP基础(3) POJ(8) UVA(14) 云服务器(1) 区间DP(4) 扩展欧几里得(1) 杂谈(2) 树状数组(1) 状态压缩DP(1) 状态空间搜索(1) 简单水题(3) 线段树(4) 背包问题(3)

/ 注册

全部文章 / 图论（共2篇）

XYZZY HDU - 1317

Floyd判断连通性 + spfa判断正环。题目描述：有一百个房间，你的初始能量值是100，从起点1开始出发，判断你能不能到达第100个房间。不能到达的情况是，在中途的过程中生命值降为0及以下，或者是没有路能够到达房间100。注意：题目中是单项边。而且同一个房间可以进入多次。解题...

2017-08-29

0 489

Rain on your Parade HDU - 2389

HK算法，匈牙利算法超时题目描述：t时间后会有一场大雨，有m个人和n个雨伞，求在ｔ时间内，使得最多的人不被雨淋。求不被雨淋的人数。解题分析：显然是匹配问题，第一次写用匈牙利算法超时了，时间复杂度n^3或n*m,之后补题，学习了Hopcroft krap算法。用Hopcropt k...

2017-07-18

0 730