POJ图论分类.pdf

《POJ图论分类.pdf》由会员分享，可在线阅读，更多相关《POJ图论分类.pdf（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、POJ 图论分类POJ 图论分类2009-07-28 23:13POJ 2449 Remmarguts Date(中等)http:/ 短路解法：dijkstra+A*(rec)，方法很多相关：http:/ POJ 3013-Big ChristmasTree(基础)http:/ 3463-Sightseeing(中等)http:/ 1 的路的数量解法：需要真正理解 dijkstraPOJ 3613-Cow Relays(较难)http:/ N 条边的最短路解法：floyd+倍增，贪心 POJ 3621-Sightseeing Cows(中等)http:/ 原始的 bellman tle,用 s

2、pfa才过)POJ 3635-full tank?(中等)http:/ 生成树问题基本的生成树就不放上来了 POJ 1639-Picnic Planning(较难)http:/ 1679-The Unique MST(基础)http:/ MST 是否唯一解法：prim 就行，不过还是易错的题 POJ 2728-DesertKing(中等)http:/ 3164-Command Network(难)http:/ 3522-Slim Span(基础)http:/ 活用连通性，度数，拓扑问题此类问题主要牵扯到 DFS，缩点等技巧 POJ 1236-Networkof Schools(基础)http:

3、/ POJ 1659-Frogs Neighborhood(基础)http:/ havel 定理 POJ 2553-TheBottom of a Graph(基础)http:/ 2186-Popular Cows(基础)http:/ 0 的点 POJ 2762-Goingfrom u to v or from v to u?(中等)http:/ 找最长链 POJ 2914-Minimum Cut(难)http:/ 算法，用网络流加枚举判定会挂 POJ2942-Knights of the Round Table(难)http:/ 3177-Redundant Paths(中等)http:/ 3

4、352-Road Construction(中等)http:/ 1236，有向图添加多少条边变成强连通图 POJ3249-Test for Job(基础)http:/ 3592-InstantaneousTransference(基础)http:/ 3687-Labeling Balls(中等)http:/ POJ 3694-Network(中等)http:/ 2-SAT 问题此类问题理解合取式的含义就不难 POJ 2723-Get LuffyOut(中等)http:/ 2749-Building roads(较难)http:/ 判定 POJ 3207-Ikkis Story IV-Panda

5、s Trick(基础)http:/ 2-sat，不过其他方法更快 POJ 3648-Wedding(中等)http:/ 3678-Katu Puzzle(基础)http:/ POJ 3683-PriestJohns Busiest Day(中等)http:/ 枚举点之间的相容性构图，求解2-SAT 最大流问题变形很多，最小割最大流定理的理解是关键 POJ 1149-PIGS(较难)http:/ POJ 1273-Drainage Ditches(基础)http:/ POJ 1459-Power Network(基础)http:/ POJ 1637-Sightseeing tour(Crazy)

6、http:/ P324POJ 1815-Friendship(中等)http:/ 1966-Cable TV Network(中等)http:/ POJ 2112-Optimal Milking(基础)http:/ POJ 2391-Ombrophobic Bovines(中等)http:/ 2396-Budget(中等)http:/ POJ 2455-Secret MilkingMachine(基础)http:/ POJ 2699-The Maximum Number of StrongKings(较难)http:/ xpcnq_71 大牛的建图的提示)POJ 2987-Firing(较难)

7、http:/ 2071-Technology Trader 也是此类型，懒了没做http:/ Room(中等，好题)http:/ POJ 3155-Hard Life(很挑战一题)http:/ 的论文(nb解法)最小割模型在信息学竞赛中的应用 一文中也有讲 POJ3189-Steady Cow Assignment(中等)http:/ SAP 的强大，纯暴力可过。更好的方法是在枚举区间的过程中不断删边和加边继续网络流过程POJ 3204-Ikkis Story I-Road Reconstruction(基础)http:/ 2532-Internship(基础)http:/ dfs 求割,或暴

8、力枚举(需要写取消某条增广路的操作(但数据弱，也许不取消也能混过)POJ 3308-Paratroopers(较难)http:/ 2125-Destroying The Graph(难)http:/ POJ 3469-Dual Core CPU(中等)http:/ POJ 3498-March of the Penguins(中等)http:/ ZOJ 2587-Unique Attack(较难)http:/ dfs 求最小割算法的本质 SPOJ 839-OptimalMarks(难)http:/www.spoj.pl/problems/OPTM/题意：略解法：很经典哦，见 amber 的集训

9、队论文，根据标号的每一位求最小割 SGU 326-Perspective(中等)http:/acm.sgu.ru/problem.php?c0&problem=326比较经典的构图法费用流问题可以 KM 解的就不放在这里，另外，感觉除非很特殊的图，一般用连续增广路的算法就够了 POJ 2175-EvacuationPlan(中等)http:/ Matrix Travels(中等)http:/ POJ 3680-Intervals(较难)http:/ 中比较详细 SPOJ 371-Boxes(简单)http:/www.spoj.pl/problems/BOXES/题意：略解法：费用流，但似乎有比

10、网络流更好的做法SGU 185-Twoshortest(中等)http:/acm.sgu.ru/problem.php?c0&problem=185题意：求两条不想交的最短路径解法：费用流，也可以最短路+最大流。匹配问题正确理解 KM 算法是很重要的这里我还要说几句：最正确解最小权匹配的办法是用一个很大的数-当前边权值，而不是直接对边权取反(这样只能处理左右点相等的完全二分图，即K(n,n)以上有可能还是说的有点问题，以后补充 POJ 1486-Sorting Slides(中等)http:/ 1904-Kings Quest(中等，好题)http:/ 2060-Taxi Cab Scheme

11、(基础)http:/ POJ 2594-Treasure Exploration(中等)http:/ POJ 3041-Asteroids(基础)http:/ 2226-Muddy Fields(基础)http:/ POJ 2195-GoingHome(基础)http:/ 算法 POJ 2400-Supervisor,Supervisee(中等)http:/ POJ 2516-Minimum Cost(中等)http:/ 算法(只有正确的才能过)，费用流(ms 错的可能也能过)POJ 3686-The Windys(较难)http:/ KM 算法去水吧，数据其实弱得不得了 O(50*50*25

12、00)-16ms相关：http:/ 412-K-path cover(较难)https:/www.spoj.pl/problems/COVER/题意：略解法：很牛叉的一道匹配相关：http:/ 206.Roads(较难)http:/acm.sgu.ru/problem.php?c0&problem=206解法：经典题目，也可以使用spoj 412 那题的优化 NP 问题一般是搜索或 dp 解的 POJ 1419-Graph Coloring(基础)http:/ POJ 2989-AllFriends(难)http:/ tle,后来找了论文：Finding All Cliques of anUndirected Graph（Coen Bron&Joep Kerboscht）ZOJ1492-Maximum Clique(基础)http:/ POJ 1470-Closest Common Ancestors(基础)http:/ 问题解法：tarjan 或 RMQ，另外输入很恶心 POJ 1985-CowMarathon(基础)http:/ 1986-Distance Queries(中等)http:/ 或 RMQ