博客首页 → hdoj

最新文章列表

[网络流]2012 acm/icpc成都网络赛hdoj 4288：Control

大致题意：    给出一个又n个点，m条边组成的无向图。给出两个点s，t。对于图中的每个点，去掉这个点都需要一定的花费。求至少多少花费才能使得s和t之间不连通。   大致思路：    最基础的拆点最大流，把每个点拆作两个点 i 和 i' 连接i->i'费用为去掉这个点的花费，如果原图中有一条边a->b则连接a'->b。对这个图求出最大流即可。     #include&l ...
2012成都网络赛acmhdoj网络流 
暴风雪 评论(0) 有1300人浏览 2012-09-16 17:03

[KM算法]hdoj 2853：Assignment

大致题意：     n个部队到m个地区抗震救灾(缅怀四川地震死难同胞)。已知每只部队到每个地区的收益值，现在给出一种匹配方案。求出达到最大匹配时的收益值比当前匹配方案多多少，且需要有多少只部队的调动不需要改动。   大致思路：     由于种种原因不能直接按照mapch数组直接来求匹配的变动数，在这里我们把所有的收益值乘以10，如果之前的方案中   i->j，则在map[i][j]上面 ...
[KM算法hdojAssignmentacm数据结构 
暴风雪 评论(0) 有807人浏览 2012-02-07 23:41

[状态压缩+最大流]hdoj 3605：Escape

大致题意：     在世界末日，有n个人要去m个星球。给出每个人能去的星球和每个星球能容纳的人数。判断是否存在可行的安排方案。n (1 <= n <= 100000), m (1 <= m <= 10) 大致思路：     以为是水题上来就直接套二分图多重匹配来做，结果被TLE到各种吐血~~ 。后来看了题解才明白，这里要用状态压缩。因为所有的人可以按照可以去的星球划分为2 ...
状态压缩最大流hdoj3605Escape 
暴风雪 评论(0) 有858人浏览 2012-01-17 18:37

[最大流]hdoj 3572：Task Schedule

大致题意：    有n个工件，已知第i个工件需要pi天加工，而且只能在第si天到第ei天加工这个工件。每天可以并行加工m个工件。求所有工件是否都能在规定期限内加工完成。大致思路：    应该算是最简单的网络流题目了吧，把工作和日期都抽象成节点，设源汇点。从源点向每一个工件连边，容量为完成工作所需要的天数。每个工作都向可以加工他的日期连边，容量为1。每个日期都向汇点连边，容量为每天可以加工工件数量的最 ...
最大流hdoj3572Task Schedule 
暴风雪 评论(0) 有1275人浏览 2012-01-17 17:31

最近博客热门TAG

Java(141744) C(73651) C++(68608) SQL(64571) C#(59609) XML(59133) HTML(59043) JavaScript(54919) .net(54785) Web(54514) 工作(54118) Linux(50905) Oracle(49875) 应用服务器(43289) Spring(40812) 编程(39454) Windows(39381) JSP(37542) MySQL(37267) 数据结构(36424)

博客人气排行榜

    博客电子书下载排行

      >>浏览更多下载

      相关资讯

      相关讨论

      Global site tag (gtag.js) - Google Analytics