标签：《挑战程序设计竞赛(第2版)》

2014-04-03阅读(6343)评论(3)

POJ 3259 Wormholes 虫洞：农夫约翰有F个农场，每个农场有N块地，其间有M条路，W条时光隧道（时间倒流）。问是否可能回到过去？ 2.5 它们其实都是“图” 最短路 依然很水很基础的 Bellman-Ford 判定负...

2014-04-01阅读(5473)评论(0)

POJ 2139 Six Degrees of Cowvin Bacon 六度空间：为了向“六度分割：你和任何一个陌生人之间所间隔的人不会超过五个”致敬，奶牛们决定拍一系列电影叫做……《六度空间》。N头牛，拍了M部电影，同一部电影中的搭档们...

2014-03-30阅读(4500)评论(0)

AOJ 0189 Convenient Location 上班族：A桑的实习办公室有多个，公司允许睡办公室，求找出一个办公室使得跑路最短。 2.5 它们其实都是“图” 最短路 基础的任意两点之间的距离Floyd-Warshall算法就行了。...

2014-03-30阅读(6275)评论(2)

最小生成树Prim算法 与Dijkstra算法类似，任意挑一个顶点，添加最短边，直至所有顶点都在树中，此时就得到一颗最小生成树了。 证明： 令V为顶点集合，已求得顶点集合为X，V上的最小生成树为T。 假设连接X和V\X的最短边为e，现在需要...

2014-03-30阅读(5636)评论(1)

对图的几种初级算法做个总结，温故知新。 最短路问题 Bellman-Ford和Dijkstra的递推公式都是d[i] = min{d[j] + cost[i to j]}。 单源最短路之Bellman-Ford算法 适用于无原点s可达负圈的...

2014-03-11阅读(5069)评论(3)

AOJ 2170: Marked Ancestor 染色祖先：距离某节点最近的染色节点称为祖先，求染色过程中各节点祖先。 2.4 加工并储存数据的数据结构 并查集 稍有些复杂，需要bfs和两棵树。一棵树用来维护并查集，一棵树用来保存原来的树...

2014-03-09阅读(7200)评论(1)

POJ 1703 Find them, Catch them 无间道：有N名来自两个帮派的坏蛋，已知一些坏蛋两两不属于同一帮派，求判断给定两个坏蛋是否属于同一帮派。 2.4 加工并储存数据的数据结构 并查集 这题真的很简单，是食物链的弱化版...

2014-03-05阅读(4770)评论(0)

POJ 2236 Wireless Network 无线网络：ACM团队只修电脑不过夜！有N台电脑坏了，它们原本组成这样一个局域网：距离d内的两台电脑互联。现在通过修理和查看操作，求查看时两台电脑是否互联？ 2.4 加工并储存数据的数据结构...

2014-03-04阅读(7377)评论(7)

POJ 2010 Moo University – Financial Aid 奶牛大学：奶大招生，从C头奶牛中招收N头。它们分别得分score_i，需要资助学费aid_i。希望新生所需资助不超过F，同时得分中位数最高。求此中位...

2014-03-04阅读(6596)评论(0)

POJ 3614 Sunscreen 奶牛美容：有C头奶牛日光浴，每头奶牛分别需要minSPF_i和maxSPF_i单位强度之间的阳光。现有L种防晒霜，分别能使阳光强度稳定为SPF_i，其瓶数为cover_i。求最多满足多少头奶牛 最小堆 ...