poj 网络流 总结

  2112 Optimal Milking

     二分+floyd+最大流验证

     floyd判断dis=0和t=dis[i][k]+dis[k][j] 顺序错了 WA了好多次

 2289 Jamie's Contact Groups

    二分+最大流验证

    数组开小会TLE，CB 打开-wall 会省去很多debug时间

2391 Ombrophobic Bovines

   数组开大TLE，要用longlong

2455 Secret Milking Machine

   依旧二分。。。。注意双向边，只要把回边容量设为c而非0即可，不要开小数组一般就没问题。手写了个HLPP模板，调死了

时间： 2024-10-09 16:22:10

poj 网络流 总结的相关文章

POJ题目分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

算法题之poj 1961 Period(KMP, 最短循环节)

题目链接: POJ  : http://poj.org/problem?id=1961 HDU : http://acm.hdu.edu.cn/showproblem.php?pid=1358 ZOJ   : http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2177 题目大意: 给定一个长度为n的字符串s,求它的每个前缀的最短循环节.换句话说,对于每个i (2<=i<=n),求一个最大的整数K>1(如果K存在),使

poj分类

初期: 一.基本算法:      (1)枚举. (poj1753,poj2965)      (2)贪心(poj1328,poj2109,poj2586)      (3)递归和分治法.      (4)递推.      (5)构造法.(poj3295)      (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法:      (1)图的深度优先遍历和广度优先遍历.      (2)最短路径算法(dijkstra,bellman-ford

HDU4292 网络流 2012 ACM/ICPC Asia Regional Chengdu Online1005

                                   Food                                          Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)                                                             Total Submission(s): 555 Acc

POJ：DNA Sorting 特殊的排序

Description One measure of ``unsortedness'' in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the letter sequence ``DAABEC'', this measure is 5, since D is greater than four letters to

POJ 1001 Exponentiation 无限大数的指数乘法 题解

POJ做的很好,本题就是要求一个无限位大的指数乘法结果. 要求基础:无限大数位相乘 额外要求:处理特殊情况的能力 -- 关键是考这个能力了. 所以本题的用例特别重要,再聪明的人也会疏忽某些用例的. 本题对程序健壮性的考查到达了变态级别了. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/ 某人贴出的测试用例数据地址: http://poj.org/showmessage?message_id=76017 有

POJ 2240 Arbitrage：最短路 Floyd

Arbitrage:http://poj.org/problem?id=2240 大意: 给你m种货币,给你m种货币兑换规则,问通过这些规则最后能不能盈利.eg:1美元换0.5英镑,1英镑换10法郎,1法郎换0.21美元,这样1美元能换0.5*10*0.21=1.05美元,净赚0.05美元. 思路: 用Floyd找出每两种钱之间的最大兑换关系,遍历一遍,看有没有那种钱币最后能盈利,有就输出Yes,没有就是No.在处理钱币名称与编号之间的关系时,可以用map存(比较好用),当然也可以用字符串比较.

POJ 1860 Currency Exchange：最短路 Bellman-Ford

Currency Exchange:http://poj.org/problem?id=1860 大意:有多种货币,之间可以交换,但是需要手续费,也就是说既有汇率又有手续费.问经过交换之后能不能赚. 思路:Bellman_Ford,因为要求最长路,所以松弛条件改一下就好了. Tips: 3              2                  1                20.0货币的数量   兑换点的数量     主人公拥有的货币量    主人公拥有货币的价值1 2 1.00

POJ 1258 Agri-Net：最小生成树 Prim 模版题

Agri-Net:http://poj.org/problem?id=1258 大意:新镇长竞选宣言就是将网络带到每一个农场,给出农场个数,两两之间建光缆的耗费,求所有都联通的最小耗费. 思路:最小生成树,因为边比较稠密,用Prim做. PS:对于比较稠密的图,用Prim,对于比较稀疏的图,用 Kruskal.Kruskal是找边的过程,稀疏的话会比较快. 更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/