您现在正在浏览：
POJ 图论[转自夏天的风blog]
发布时间：
10:22:42 &
浏览次数：
摘要： POJ 2060-Taxi Cab Scheme(基础)AC http://acm./JudgeOnline/problem?id=2060题意：最小路径覆...
POJ 图论【转自夏天的风blog】
杂题
POJ 2449 Remmarguts' Date(中等)
AC
http://acm./JudgeOnline/problemid=2449
题意：经典问题：K短路
解法：dijkstra+A*(rec)，方法很多
相关：http://acm./JudgeOnline/showcontestcontest_id=1144
该题亦放在搜索推荐题中
POJ 3013 - Big Christmas Tree(基础)
AC
http://acm./JudgeOnline/problemid=3013
题意：最简单最短路，但此题要过，需要较好的程序速度和，还要注意精度
解法：Dijkstra
POJ 3463 - Sightseeing(中等)
AC
http://acm./JudgeOnline/problemid=3463
题意：最短路和比最短路大1的路的数量
解法：需要真正理解dijkstra
POJ 3613 - Cow Relays(较难)
AC
http://acm./JudgeOnline/problemid=3613
题意：求经过N条边的最短路
解法：floyd + 倍增，贪心
POJ 3621 - Sightseeing Cows(中等)
AC
http://acm./JudgeOnline/problemid=3621
题意：求一个环路，欢乐值 / 总路径最大
解法：参数搜索 + 最短路(ms 原始的bellman tle, 用spfa才过)
POJ 3635 - full tank(中等)
AC
http://acm./JudgeOnline/problemid=3635
题意：最短路变形
解法：广搜
相关：/hnu_reason/blog/item/086e3dccfc8cbb.html
生成树问题
基本的生成树就不放上来了
POJ 1639 - Picnic Planning(较难) AC
http://acm./JudgeOnline/problemid=1639
题意：顶点度数有限制的最小生成树
解法：贪心 + prim/kruskal
POJ 1679 - The Unique MST(基础)
AC
http://acm./JudgeOnline/problemid=1679
题意：判断MST是否唯一
解法：prim就行，不过还是易错的题
POJ 2728 - Desert King(中等)
AC
http://acm./JudgeOnline/problemid=2728
题意：所谓最优比率生成树
解法：参数搜索 + prim
POJ 3164 - Command Network(难) AC
http://acm./JudgeOnline/problemid=3164
题意：最小树形图
解法：刘朱算法，这个考到的可能性比较小吧？
POJ 3522 - Slim Span(基础)
AC
http://acm./JudgeOnline/problemid=3522
题意：求一颗生成树，让最大边最小边差值最小
解法：kruskal活用
连通性，度数，拓扑问题
此类问题主要牵扯到DFS，缩点等技巧
POJ 1236 - Network of Schools(基础)
AC
http://acm./JudgeOnline/problemid=1236
题意：问添加多少边可成为完全连通图
解法：缩点，看度数
POJ 1659 - Frogs' Neighborhood(基础) AC
http://acm./JudgeOnline/problemid=1659
题意：根据度序列构造图
解法：贪心，详细证明参见havel定理
POJ 2553 - The Bottom of a Graph(基础)
（好题）
http://acm./JudgeOnline/problemid=2553
出度为0的强连通分量的所有的点
POJ 2186 - Popular Cows(基础)
（好题）
http://acm./JudgeOnline/problemid=2186
题意：强连通分量缩点图出度为0的点
POJ 2762 - Going from u to v or from v to u(中等) AC
http://acm./JudgeOnline/problemid=2762
题意：单向连通图判定
解法：缩点 + dp找最长链 (我是用 缩点+ 欧拉路判断，最后证明这方法是错的)
POJ 2914 - Minimum Cut(难) AC
（难）
http://acm./JudgeOnline/problemid=2914
题意：无向图最小割
解法：Stoer-Wagner算法，用网络流加枚举判定会挂
POJ 2942 - Knights of the Round Table(难) AC
http://acm./JudgeOnline/problemid=2942
题意：求双联通分量(或称块)中是否含奇圈
解法：求出双连通分量后做黑白染色进行二分图图判定
相关：/zfy0701/blog/item/57ada7ed104ce9d2b31cb104.html
POJ 3177 - Redundant Paths(中等) AC
http://acm./JudgeOnline/problemid=3177 （和3352一样）
题意：添加多少条边可成为双向连通图（任意两点间有两条不共边的路径）
解法：把割边分开的不同分量缩点构树，看入度
公式： 入度为1的leaf个数， ( leaf + 1 ) / 2
POJ 3352 - Road Construction(中等) AC
http://acm./JudgeOnline/problemid=3352 （和3177一样）
题意：添加多少条边可成为双向连通图（当删除任意一条边的时候，图还保持连通性）
解法：把割边分开的不同分量缩点构树，看入度 ( leaf + 1 ) / 2
建议对比下1236，有向图添加多少条边变成强连通图
POJ 3249 - Test for Job(基础)
http://acm./JudgeOnline/problemid=3249
解法：bfs / dfs + dp
POJ 3592 - Instantaneous Transference(基础) AC
http://acm./JudgeOnline/problemid=3592
解法：缩点，最长路，少人做的水题，注意细节 （和 3160 类似）
POJ 3687 - Labeling Balls(中等)
（莫名其妙，有空再重新看）
http://acm./JudgeOnline/problemid=3687
解法：拓扑排序
POJ 3694 - Network(中等) AC
http://acm./JudgeOnline/problemid=3694
解法：双连通分量+并查集
2-SAT问题
此类问题理解合取式的含义就不难
POJ 2723 - Get Luffy Out(中等) AC （好题）
http://acm./JudgeOnline/problemid=2723
解法：二分 + 2-SAT判定
POJ 2749 - Building roads(较难) AC
http://acm./JudgeOnline/problemid=2749
解法：二分 + 2-SAT判定
POJ 3207 - Ikki's Story IV - Panda's Trick(基础) AC
http://acm./JudgeOnline/problemid=3207
解法：简单的2-sat，不过其他方法更快
POJ 3648- Wedding(中等) AC
http://acm./JudgeOnline/problemid=3648
解法：用2-sat做会比较有意思，但是暴搜照样0ms
POJ 3678 - Katu Puzzle(基础) AC
http://acm./JudgeOnline/problemid=3678
解法：直接按合取式构图验证就行了（本质）
POJ 3683 - Priest John's Busiest Day(中等) AC
http://acm./JudgeOnline/problemid=3683
解法：n^2枚举点之间的相容性构图，求解2-SAT (要求输出方案)
POJ 2296 Map Labeler (中等)
(第七道)AC
http://poj.org/problemid=2296
解法：上下边形成2元关系。然后构完图，求2-SAT
POJ 3905 Perfect Election(中等) (第八道) AC
http://poj.org/problemid=3905（好题！）
解法: 建好矛盾，直接就是2-SAT
最大流问题
变形很多，最小割最大流定理的理解是关键
POJ 1149 - PIGS(较难) AC
（灰常好题！强烈推荐）
http://acm./JudgeOnline/problemid=1149
绝对经典的构图题
POJ 1273 - Drainage Ditches(基础) AC
http://acm./JudgeOnline/problemid=1273
最大流入门
POJ 1459 - Power Network(基础) AC
http://acm./JudgeOnline/problemid=1459
基本构图
POJ 1637 - Sightseeing tour(Crazy) AC
http://acm./JudgeOnline/problemid=1637
题意：求混合图的欧拉迹是否存在
解法：无向边任意定向，构图，详建黑书P324
POJ 1815 - Friendship(中等) AC
http://acm./JudgeOnline/problemi1d=815
题意：求最小点割
解法：拆点转换为边割
相关：/zfy0701/blog/item/a521f230b06dea9fa9018e0e.html
POJ 1966 - Cable TV Network(中等) AC
http://acm./JudgeOnline/problemid=1966
题意：去掉多少点让图不连通
解法：任定一源点，枚举汇点求点割集(转换到求边割)，求其中最小的点割
POJ 2112 - Optimal Milking(基础) AC
（好题）
http://acm./JudgeOnline/problemid=2112
二分枚举，最大流
POJ 2391 - Ombrophobic Bovines(中等) AC
（好题）
http://acm./JudgeOnline/problemid=2391
题意：floyd, 拆点，二分枚举
相关：/zfy0701/blog/item/3ef0eaf8226acff.html
POJ 2396 - Budget(中等)
http://acm./JudgeOnline/problemid=2396
题意：有源汇的上下界可行流
解法：用矩阵-网络流模型构图，然后拆边
相关：/zfy0701/blog/item/e15e3e5343c1ba.html
最小割模型在竞赛中的应用
POJ 2455 - Secret Milking Machine(基础) AC
（好题）
http://acm./JudgeOnline/problemid=2455
二分枚举，一般来说需要写对边容量的更新操作而不是每次全部重新构图
POJ 2699 - The Maximum Number of Strong Kings(较难)
http://acm./JudgeOnline/problemid=2699
解法：枚举人数 + 最大流(感谢xpcnq_71大牛的建图的提示)
POJ 2987 - Firing(较难)
（经典）
http://acm./JudgeOnline/problemid=2987
题意：最大权闭包
解法：先边权放大，第一问总量-最大流，第二问求最小割
相关：http://wywcgs./blog/cns!4D861A02A9.entry&_c02_owner=1
RQNOJ 最大获利Profit(中等) AC
（经典）
/Problem_556.html
最大权闭包图的特殊情况
ZOJ 2071 - Technology Trader
AC
http://acm./onlinejudge/showProblem.doproblemCode=2071
也是此类型，最大权闭包图。 多加了输出 买哪些组件，使效益最大。
POJ 3084 - Panic Room(中等，好题)
http://acm./JudgeOnline/problemid=3084
题意：略
解法：根据最小割建模
POJ 3155 - Hard Life(很挑战一题) AC
（难）
http://acm./JudgeOnline/problemid=3155
题意：最大密度子图
解法：参数搜索 + 最大权闭合图，A.V.Goldberg的论文(nb解法)
最小割模型在信息学竞赛中的应用 一文中也有讲
POJ 3189 - Steady Cow Assignment(中等) AC
http://acm./JudgeOnline/problemid=3189
题意：寻找最小的区间完成匹配
解法：这题充分说明SAP的强大，纯暴力可过。更好的方法是在枚举区间的过程中不断删边和加边继续网络流过程
POJ 3204 - Ikki's Story I - Road Reconstruction(基础)
http://acm./JudgeOnline/problemid=3204
ZOJ 2532 - Internship(基础)
http://acm./onlinejudge/showProblem.doproblemCode=2532
题意：确定边是否是某个割中的边
解法：两边dfs求割, 或暴力枚举(需要写取消某条增广路的操作(但数据弱，也许不取消也能混过))
POJ 3308 - Paratroopers(较难)
http://acm./JudgeOnline/problemid=3308
POJ 2125 - Destroying The Graph(难)
http://acm./JudgeOnline/problemid=2125
题意：最小点权覆盖
POJ 3469 - Dual Core CPU(中等)
http://acm./JudgeOnline/problemid=3469
题意：最小割
POJ 3498 - March of the Penguins(中等)
http://acm./JudgeOnline/problemid=3498
题意：满足点容量限制的网络流
解法：拆点把点容量转换为边容量，枚举汇点
ZOJ 2587 - Unique Attack(较难)
http://acm./show_problem.phppid=2587
题意：确定最小割是否是唯一的
解法：得理解dfs求最小割算法的本质
SPOJ 839 - Optimal Marks(难)
http://www.spoj.pl/problems/OPTM/
题意：略
解法：很经典哦，见amber的集训队论文，根据标号的每一位求最小割
SGU 326 - Perspective(中等)
http://acm.sgu.ru/problem.phpc0&problem=326
比较经典的构图法
费用流问题
可以KM解的就不放在这里，另外，感觉除非很特殊的图，一般用连续增广路的算法就够了
POJ 2175 - Evacuation Plan(中等)
http://acm./JudgeOnline/problemid=2175
题意：判断是否给定解是最优解，比较阴的一题
解法：根据给出的计划构造流，然后消且只消一次负圈
POJ 3422 - Kaka's Matrix Travels(中等)
http://acm./JudgeOnline/problemid=3422
题意：略
解法：拆点
POJ 3680 - Intervals(较难)
http://acm./JudgeOnline/problemid=3680
题意：略，这题还是蛮经典
解法：discuss中比较详细
SPOJ 371 - Boxes(简单)
http://www.spoj.pl/problems/BOXES/
题意：略
解法：费用流，但似乎有比网络流更好的做法
SGU 185 - Two shortest(中等)
http://acm.sgu.ru/problem.phpc0&problem=185
题意：求两条不想交的最短路径
解法：费用流，也可以最短路 + 最大流。
匹配问题
正确理解KM算法是很重要的
这里我还要说几句：最正确解最小权匹配的办法是用一个很大的数-当前边权值，而不是直接对边权取反(这样只能处理左右点相等的完全二分图，即K(n, n)
以上有可能还是说的有点问题，以后补充
POJ 1486 - Sorting Slides(中等) AC
http://acm./JudgeOnline/problemid=1486
题意：二分图的必须边
解法：需正真理解最大匹配算法，详见/kevin0602/blog/item/1d5be63b5bec9bec14cecb44.html
POJ 1904 - King's Quest(中等，好题) AC
http://acm./JudgeOnline/problemid=1904
题意：求二分图所有可能的匹配边
解法：虽然最终不是用匹配算法，但需要理解匹配的思想转换成强连通分量问题。
POJ 2060 -Taxi Cab Scheme(基础) AC
http://acm./JudgeOnline/problemid=2060
题意：最小路径覆盖
POJ 2594 -Treasure Exploration(中等) AC
http://acm./JudgeOnline/problemid=2594
题意：可相交最小路径覆盖
解法：先传递闭包转化下
POJ 3041 - Asteroids(基础) AC
http://acm./JudgeOnline/problemid=3041
解法: 简单行列匹配
POJ 2226 - Muddy Fields(基础) AC
http://acm./JudgeOnline/problemid=2226
题意：行列的覆盖
解法：最小点集覆盖 = 最大匹配
POJ 2195 - Going Home(基础) AC
http://acm./JudgeOnline/problemid=2195
题意：最小权值匹配
解法：KM算法
POJ 2400 - Supervisor, Supervisee(中等) AC
http://acm./JudgeOnline/problemid=2400
题意：输出所有最小权匹配
解法：KM, 然后回溯解，汗，输入的两个矩阵居然是反过来的
POJ 2516 -Minimum Cost(中等) AC
http://acm./JudgeOnline/problemid=2516
题意：最小权值匹配或最小费用流
解法：拆点 + KM算法(只有正确的才能过)，费用流(ms错的可能也能过)
POJ 3686 - The Windy's(较难) AC
http://acm./JudgeOnline/problemid=3686
题意：最小权值匹配
解法：拆点,然后尽管用KM算法去水吧，数据其实弱得不得了 O(50 * 50 * 2500) -> 16ms
相关：/kevin0602/blog/item/3b087bec2c97.html
SPOJ 412 - K-path cover(较难)
https://www.spoj.pl/problems/COVER/
题意：略
解法：很牛叉的一道匹配
相关：/roba/blog/item/c842fdfac10d24dcb48f31d7.html
SGU 206. Roads(较难)
http://acm.sgu.ru/problem.phpc0&problem=206
解法：经典题目，也可以使用spoj 412那题的优化
NP问题
一般是搜索或dp解的
POJ 1419 - Graph Coloring(基础)
http://acm./JudgeOnline/problemid=1419
题意：图的着色
解法：搜索，可惜题目的数据真是太弱了
POJ 2989 - All Friends(难)
http://acm./JudgeOnline/problemid=2989
题意：极大团数量
解法：开始狂tle, 后来找了论文：Finding All Cliques of an Undirected Graph（Coen Bron & Joep Kerboscht）
ZOJ 1492 - Maximum Clique(基础) AC
http://acm./show_problem.phppid=1492
题意：图的最大团
解法：搜索，如果要求速度，可参考下相应论文
其他
不能成大类的
POJ 1470 - Closest Common Ancestors(基础)
http://acm./JudgeOnline/problemid=1470
题意：LCA问题
解法：tarjan或RMQ，另外输入很恶心
POJ 1985 - Cow Marathon(基础)
http://acm./JudgeOnline/problemid=1985
题意：树上的最长路径
解法：dp
POJ 1986 - Distance Queries(中等)
http://acm./JudgeOnline/problemid=1986
题意：LCA
解法：tarjan或RMQ
HOJ 11192 - Justice League(有趣的图论)
:8080/online/action=problem&type=show&id=11192&courseid=99
HOJ 11277 - New Island(有趣的图论)
:8080/online/action=problem&type=show&id=11277&courseid=109
本文转载自: http://blog.csdn.net/logic_nut/archive//4491326.aspx
====================================================================================================
1062* 昂贵的聘礼
解法：枚举等级限制+最短路
交易过程中等级最高和最低的差小于m
1087* A Plug for UNIX (HDU1526)
解法：2分匹配
调制器无限，用floyd传递插口转换，然后就是2分匹配
1094 Sorting It All Out
解法：floyd + 拓扑排序
先用floyd判断自环（或用Tarjan），拓扑判断是否能确定序列
1112* Team Them Up! 2分图染色+DP (ZOJ1462)
1125 Stockbroker Grapevine
解法：floyd
FLOYD,然后求每个点到其他点的最短时间和
1135 Domino Effect
(ZOJ1298)
题意：有n个关键骨牌 (1 <= n < 500)，m列骨牌。整个多米诺骨牌图是联通的。
m列骨牌描述如下：a,b,i，表示这排骨牌是在关键骨牌a到b之间的，从一头到另一头倒下需要i秒。
总是从n=1的骨牌开始推倒。 输出最后倒下的骨牌的倒下时间和位置（最后倒下的是某个关键骨牌，或者某两个关键骨牌之间）
数据二的图形，可看出，最后倒的在2,3中间位置。
解法：最短路
求出骨牌1到其他骨牌的最短路，最后倒下的是某个关键骨牌，或者某两个关键骨牌之间
1149* PIGS
题意：有M个猪圈(M<=1000),每个猪圈里初始时有若干头猪
一开始所有的猪圈都是关闭的.
一次来了N个顾客(N<=100) , 每个顾客分别会打开指定的几个猪圈,从中买若干头猪
每个顾客分别有他能够买的数量的上限.
每个顾客走后,他打开的猪圈中的猪可以任意给调换到其他开着的猪圈里,然后所有猪圈从新关上.
问:总共最多能卖出多少头猪.
解法：分层网络流
可以把猪圈分层建边，但是节点数要10W。有更优秀的建边方法
请移步这里
1161* Walls
解法：floyd
将区域作为顶点，如果两个区域邻接(有公共边)，就连边，权值为1
注意:输入区域的点的顺序(顺逆时针)
以此建图，用floyd算法算出每个顶点间的最短距离,然后就是穷举每个顶点。
使每个俱乐部的成员到(所在村庄)达该顶点的距离之和最小
村庄到区域的距离即：将村庄作为点的区域(顶点)到枚举顶点的距离
1201 Intervals
解法：差分约束
约束条件：s[b]-s[a-1] >= c
， 0
<= s[i+1]-s[i] <= 1
1236* Network of Schools
题意：问添加多少边可成为完全连通图
解法：基础强联通
缩点，看度数
1251 Jungle Roads
解法：基础最小生成树
1273 Drainage Ditches
解法：基础最大流
注意输入时先输边数n，再是点数m
1274 The Perfect Stall
题意：牛和挤奶器最大匹配
解法：基础二分匹配
1275* Cashier Employment
(神题)
解法：差分约束
ti[i] 表示从 i 开始工作的人数 ，s[i]
表示 0-i 总共雇佣了多少人 ， r[i]
表示 i 所需的至少人数
ti[i-7]+ti[i-6]+...ti[i]
>= r[i]
( 表示前8小时开始工作的人数 )
设：s[i]-s[i-8]
= ti[i-7]+ti[i-6]+...ti[i]
0 <= S[i]-S[i-1]
<= ti[i]
约束条件：①S[i]-S[i-1]
>= 0
②S[i-1]-S[i] >= -ti[i]
③S[i]-S[i-8] >= r[i] ( i>=8 )
④S[23]+S[a]-S[a+16] >= r[i] ( i S[a]-S[a+16]
>= r[i]-S[23]
⑤*注意：S[24]-S[0]>=mid
//这句话要记得
1325 Machine Schedule
解法： 二分匹配(最小点覆盖)
最小点覆盖：选取最少的点数，使这些点和所有的边都有关联（选择最少的点覆盖所有的边）
1364 King
解法：差分约束
gt： s[a+b]-s[a-1]>c
==>
s[a+b]-s[a-1]>=c+1
lt： s[a+b]-s[a-1]
s[a-1]-s[a+b]>(-c)
超级源点： s[i]-s[n+1] >= 0
1422 Air Raid
解法：二分匹配 (最小路径覆盖)
（伞兵） 最小路径覆盖：用最少的不相交简单路径覆盖所有结点。
有向图：ans = n - match() ， 无向图： ans = n - ( match() +1 ) / 21459 Power Network
解法：基础网络流
1466 Girls and Boys
解法：二分匹配 ( 最大独立集 )
最大独立集 = 顶点数 - 最小点覆盖
由于最小点覆盖所有边，所以去掉这些点后，剩下的点之间就没有关联边，即互相独立
1469 COURSES
(HDU1083)
解法：二分匹配(完全匹配 )
1502 MPI Maelstrom
题意：计算从1发送信息到其他n-1个点最短时间 , 并且信息是同时发出去的
解法：最短路
计算1到其他n-1个点的最短时间，再取最大即可(因为信息是同时发的)
1511* Invitation Cards (HDU1535)
解法：最短路
来回最短路(单向):
正向建边 , 可以计算出S到任意点的最短路。
反向建边,那么S到任意点的最短路就相当于从任意点回来S的最短路
1548 Robots
解法：二分匹配(有向无环图的最小路径覆盖)
1566 The Doors
解法：计算几何+最短路
1637* Sightseeing tour
解法：混合欧拉回路
单向边：无用，删
in[b]++ ; out[a]++
双向边：随意定向
in[b]++ ; out[a]++
【建图】x = in[i]-out[i]
①如果x是奇数，肯定不存在欧拉回路
②如果x>0 (入>出) 连 i -> T
容量： x/2
③如果x<0 (入 i
容量：-x/2
【判断】是否满流
1698 Alice's Chance
题意：有N个film，Alice想要参加所以film的主演。
给出每个film在每个星期的开拍时间，和需要拍的天数，并且给出期限日期。
问Alice是否能合理安排时间，完成所有的film的拍摄工作。
解法：多重匹配
X部为:7*50天,Y部为每个film.容量为需要的天数D[i] .
建边:对于每个film,从第一个星期开始每个星期的可以拍的时间和Y部连一条边.一直到期限日期那一个星期结束连边.然后求一次多重匹配.判断是否是完美匹配.
1716 Integer Intervals
题意：和1201一样
解法：差分约束
① s[b+1]-s[a]>=2
② 0 <= s[i+1]-s[i] <= 1
③ s[i]>=0 (第③个是建超级源点的条件，这里可以不要)
1719 Shooting Contest
题意：有r行c列的矩阵。每一列都有2个白格子。现在要求你射击c次，使得每一列都被射击正好一次。并且每一行至少都射击一次。
求是否有解，并输出每一列射击的相应行坐标。
解法：二分匹配（行列匹配）
X部为行，Y部为列。先进行一次行列匹配。判断是否match() == r 。如果是，说明每一行都对应了一列。那么剩下的未匹配的列，进行随意行跟它匹配即可。这样就可以使得每一行都没匹配过，并且每一列都仅被匹配了一次。
1724* ROADS
解法：带限制的最短路
方法①
将每个点拆分，开二维 dis[ i ][ j ] 记录。表示到达节点 i 总共花费 j 的金钱所需的最短路 ( j<=K )
方法②广搜bfs() + 优先队列
1734 Sightseeing trip
解法：Floyd
求最小环 + 输出路径
[cpp] view
plaincopy
void floyd() { // 最小环模板
int i,j,k,w,v;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) path[i][j]=j,dis[i][j]=e[i][j];
for(k=1;k<=n;k++) {
//新增部分,求最小环
for(i=1;ifor(j=1;jif(dis[i][j]==inf)
if(d>dis[i][j]+e[i][k]+e[k][j]) {
d=dis[i][j]+e[i][k]+e[k][j];
// 记录路径
len=0; s[0]=k; v=i;
while(v!=j) s[++len]=v,v=path[v][j];
s[++len]=j;
//通常的floyd部分
for(i=1;i<=n;i++) if(dis[i][k]!=inf)
for(j=1;j<=n;j++) if(dis[k][j]!=inf)
if(dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=w , path[i][j]=path[i][k];
1780* Code
（好题）
题意：要求所有的n位数编码成一个数字串，每个n位数只出现一次
解法：欧拉回路
可以把n位数看成边，那么可以把它的前n-1位看成点A，后n-1一位看成点B，
那么它就是A->B的一条边。找一次欧拉回路就行了。
此题要用栈模拟递归函数！！！
1789 Truck History
解法：最小生成树( prim 或 kruskal)
1797 Heavy Transportation
解法：最小生成树 或 最短路 或 dfs
二分枚举下限，用最小生成树 或 最短路 或 dfs 判断 1 和 n 是否连通
1847 Tram
解法：简单最短路
1860 Currency Exchange
题意：货币兑换
解法：Bellman-Ford 判环
1904* King's Quest
解法：强连通
不是很明白...
1949 Chores
解法：最短路
反向建图
建立超级源点S=0
，连接入度为0 的点，边权为 0
点 i 和
prerequisites ( j ) ， i 连 j ，边权为 time[ i ]
然后求最长路
PS: 正向建边，不知道哪里错了，一直TLE
2060 Taxi Cab Scheme
解法：二分匹配 (最小路径覆盖)
2075 Tangled in Cables
解法：最小生成树
2112 Optimal Milking
解法：二分+网络流
二分最远距离，建可行边，判断是否符合要求
2125 Destroying The Graph
解法：最小割(最小点权覆盖)
最小点权覆盖：最小点权覆盖所有的边 （等同于最大独立集）
拆点并将点权转成边权。
i 和 i+n 分别表示出入，S 连 i 删出边的权， i+n 连 T 删入边的权。 求最小割。
2135 Farm Tour
题意：无向图，从起点到终点，再从终点到起点。不能走重复的边。求最短路程。
解法：费用流
相当于找两条从起点到终点不重复的路径。
S 连起点，容量2 费用0 ，
终点连 T，容量2 费用0
拆边：
i 连 j ，j 连 i 容量1 ， 费用边权w
2139 Six Degrees of Cowvin Bacon
题意：
类似 HDU1869 六度分离
这里求的是以哪个人 i 为中心，到其他人的分离度的平均值最小，求最小值
解法： Floyd
相当于求 i 到其他人的距离总和最小， 最后 avg = sum*100 / (n-1) 即可
2226 Muddy Fields
题意：用最少的木板覆盖所有的muddy，且木板不能覆盖到草地
解法：二分匹配 (行列匹配)
拆行和拆列(一行拆成多行)，把每一行连续的 * 看做一“行”，把每一列连续的 * 看做一“列”
再对每一个 * 所对应的 “行” 和 “列” 连边，求二分匹配
2230 Watchcow
题意：无向图，从1出发经过每条边2次回到1。输出路径
解法：欧拉回路
拆无向边为有向边，a->b b->a ，就变成了每条边经过一次的欧拉回路。从1做一次欧拉就可以了
2239 Selecting Courses
解法： 基础二分匹配
2240 Arbitrage
题意：货币兑换
解法：Bellman-Ford(或Floyd)
2253 Frogger
解法：二分+最短路
2267* From Dusk till Dawn or: Vladimir the Vampire 最短路
2289 Jamie's Contact Groups
(HDU1669)
解法：二分+二分图多重匹配 (或 二分答案+网络流)
2296 Map Labeler
解法：2-Sat (二分枚举答案)
2312 Battle City
题意：给以图,坦克能不能走到目标位置.
解法：上下左右连边，然后最短路一下就可以了(或者直接用BFS)
2337 Catenyms
解法：欧拉路径
①用并查集判断连通性
②判断入度和出度是否满足
欧拉回路-> 入度=出度
欧拉路径-> 只有一个,入度-出度=1 ; 只有一个,出度-入度=1
2349 Arctic Network
题意： 有卫星电台的城市之间可以任意联络。没有卫星电台的城市只能和距离小于等于D的城市联络。题目告诉你卫星电台的个数S，让你求最小的D.
做最小生成树，去掉最长的S条边后，剩下最长的边就是D.
也就是求最小生成树中第S+1长的边。
解法：最小生成树
2353 Frogger
解法：最短路(或最小生成树)
2367 Genealogical tree
解法：基础拓扑排序
2387 Til the Cows Come Home
解法：基础最短路
2391* Ombrophobic Bovines
解法：二分+网络流
S 连 i (牛)
容量: 牛的数量
i+n (棚) 连 T 容量: 能hold牛的个数
i 连 j+n 容量:inf
(表示可行流)
PS:
const ll inf=9999
up=inf (上界)
WA
up=9999ll
AC
2394 Checking an Alibi
题意： 给你无向图，两点间花费的时间。再给你每个牛所在的位置。
给定一个time ， 问你哪些牛可以在time时间内到达 1解法：最短路
2396* Budget 上下界网络流
2421* Constructing Roads
解法：基础最小生成树
2446 Chessboard
题意：去掉k个洞，剩下的点能不能用1X2的矩形完全覆盖
解法：二分匹配
相连的2点进行匹配，判断是否是完全匹配
2455 Secret Milking Machine
解法：二分+网络流
注意重边也要！
2457 Part Acquisition
解法：最短路 (输出路径)
miles to Chicago
解法：最短路
求边乘积最大，将其化成对数，就是加起来最大。让后就是裸的最长路了
2485 Highways
解法：基础最小生成树
2502 Subway
解法：最短路
2516 Minimum Cost 费用流
2536 Gopher II
解法：基础二分匹配
2553* The Bottom of a Graph
解法：强连通出度为0的点，它们能到达的点V，V都能到达它们
2570 Fiber Network
解法：最短路预处理+位运算 ( 好题啊! )
2584 T-Shirt Gumbo
解法：多重匹配
2594* Treasure Exploration
解法：floyd传递性+二分匹配(最小路径覆盖)
2672 Hotkeys
2723 Get Luffy Out
解法：二分+2-Sat
2-Sat的本质就是：一件物品选了，对另一件物品的影响。
每个物品有2个状态： 选，不选 。即 x 和 ~x
如 x y 。选了x，y钥匙就会消失。那么选了x就不能选y， 即选了x就选 ~y (非y)
2724 Purifying Machine 2分匹配
2728 Desert King 最优比例生成树
2749* Building roads (好题!)
解法：二分+2-Sat
建矛盾: hate的必须分开,
like的必须栓在同一个点
距离矛盾：① dis1[ i ] + dis1[ j ] > mid
② dis2[ i ] + dis2[ j ] > mid
③ dis1[ i ] + dis2[ j ] + dis > mid
④ dis2[ i ] + dis1[ j ] + dis > mid
记：dis1 表示 cow 到 s1 的距离 ， dis2 表示 cow 到 s2 的距离 ， dis 表示 s1 到 s2 的距离。
2762 Going from u to v or from v to u
解法：强连通+拓扑
强连通缩点，同一分量的不需要考虑了。
不属于同一强连通分支的点就用拓扑排序来判断，如果某次删除点的时候发现两个入度为0的点，则说明这两个点只能由已经被删掉的点到达。
也就是说这两个点互相不可达。所以只要同时出现了多于一个的0入度的点，那么这个图一定是不符合题目要求的，输出"No".
注：用欧拉路径判断是错的，以下数据
5 8
1 2
5 4
2949* Word Rings
解法：最优比率环
2983 Is the Information Reliable
解法：差分约束
P:
c<=s[a]-s[b]<=c
V:
1<=s[a]-s[b]
超级源点： addedge( 0 , i , 0 )
注意：不要忘记建超级源点！！！
2987 Firing 最小割(求解正确性)
3020 Antenna Placement
题意：用最小的1X2的椭圆覆盖所有的点。
解法：二分匹配(黑白匹配变形)
先进行黑白(奇偶)进行一次匹配。那么剩下的未匹配的点，每个就都需要一个椭圆去覆盖。已经匹配的每一对只要一个椭圆去覆盖。所以最好的答案就是： ( tot(*点的总数) - 2*match() ) + match() ;
3037 Skiing
解法：带限制的最短路 ( 或者 BFS+优先队列 )
由于速度变化过程中，最小为-50倍，最大为50倍。
所以，dis[N][D]开二维，表示到达第i个点，速度变为（D-50）倍的最短时间。
然后直接最短路或者BFS搞之。
3041 Asteroids
解法：二分匹配
3072* Robot
解法:计算几何+最短路
dis[ u ][ v ] 表示从u到v的状态下，最短时间。
转移
dis[ u ][ v ] = min( dis[ u ] [ v ] , dis[ j ] [u ] + w + turn( p[j] , p[u] , p[u]
, p[v] ) ) ; { 1<=j<=n }
turn( p[j] , p[u] , p[u] , p[v] ) 用来计算向量 p[j]p[u] 和向量 p[u]p[v]
的夹角。
3114 Countries in War
解法：强联通+最短路
3159 Candies
解法：差分约束
dis[i]表示第i个kid拿到的糖果数。dis[b]-dis[a]<=c ，求dis[n]-dis[1]的最大值。 addedge(a,b,c)
(spfa过不了...要用dijkstra+优先队列(什么堆优化的都可以)才可以...)
3160 Father Christmas flymouse
解法：强联通+最长路
3164 Command Network
解法：最小树形图（有根树）3169 Layout
题意：N只牛按顺序从左到右站成一排；
并且 牛a喜欢牛b，那么他们之间的距离不能超过d；
牛a不喜欢牛b，那么他们之间的距离至少要d。
解法：差分约束
like
0<=dis[b]-dis[a]<=c
==> dis[b]-dis[a]<=c
==> dis[a]-dis[b]<=0
hate
dis[b]-dis[a]>=c
==> dis[a]-dis[b]<=-c
dis[i+1]-dis[i]>=0
==> dis[i]-dis[i+1]<=0
3177 Redundant Paths
解法：边双连通分量
至少要加多少条边，使得图中没有桥边
边双连通缩图之后，叶子结点leaf。那么至少需要加 (leaf+1) / 2 条边，才能使得每条边都至少属于一个环，即没有桥边。
3189 Steady Cow Assignment
题意：有N头牛，B个棚。每头牛对每个棚有个偏好（第一偏好，第二偏好。。。），并且每个棚有一定的容纳量。
现在要你安排牛到每个棚中，使得 牛的最大偏好那个和最小偏好的牛的差值最小。
解法：枚举偏好区间+多重匹配
枚举偏好值[ l , r ] , 然后对每个牛偏好在 l ~ r 对应的棚进行多重匹配判断是否完美匹配。然后取最小差值即可。
3204 Ikki's Story I - Road Reconstruction 最大流
3207 Ikki's Story IV - Panda's Trick
解法：2-SAT
3216 Repairing Company
解法：二分匹配+最短路
给出每个人物的维修位置pi,开始时间ti,结束时间di.求需要最少的工人完成所有维修工作.最短路+最小路径覆盖
3228 Gold Transportation 网络流
3255 Roadblocks
解法：最短路+A*求第2短路
3259 Wormholes
解法：Bellman求负权回路3268 Silver Cow Party
解法:最短路(正反向建边)
3275 Ranking the Cows dfs
3281 Dining 最大流 3308 Paratroopers 最小割
3310 Caterpillar
3311 Hie with the Pie
解法：Floyd+状压DP
[cpp] view
plaincopy
//dp[i][j]
:表示状态i,到达j点的最短路时间
:表示缩图后的u->v的最短距离
:保存经过1~n的点后回到原点0的最短路
int state=(1<for(i=0;ifor(int u=1;u<=n;u++) {
if(i==0) dp[i|pw[u-1]][u]=g[0][u];
for(int v=1;v<=n;v++) {
if(i&pw[v-1])
dp[i|pw[v-1]][v]=min(dp[i|pw[v-1]][v],dp[i][u]+g[u][v]);
for(i=1;i<=n;i++) ret=min(ret,dp[pw[n]-1][i]+g[i][0]);
3328 Cliff Climbing
解法：BFS(或者用最短路)3343 Against Mammoths
解法：二分+二分匹配
3352 Road Construction
解法：边双连通分量
至少要加多少条边，使得图中没有桥边
边双连通缩图之后，叶子结点leaf。那么至少需要加 (leaf+1) / 2 条边，才能使得每条边都至少属于一个环，即没有桥边。
3439 Server Relocation
解法：最短路
3463 Sightseeing
解法：最短路
Dijkstra求最短路和次短路条数。3469 Dual Core CPU 最小割
3487 The Stable Marriage Problem
解法：稳定婚姻
3521 Geometric Map 计算几何+最短路
3522 Slim Span 最小生成树
解法：最小生成树
MST的最大，最小边差值最小
枚举最小边，然后求MST，保存最小差值。
3549 GSM phone 计算几何+最短路
3565 Ants
题意：给定2*N个点的坐标，让你用前N个点和后N个点一一配对，使得相连的边没有相交的。
解法：KM匹配
首先有一个性质必须知道，那就是最短的配对，必然是没有相交的。于是我们就可以构建二分图，求最小权匹配。
根据三角形不等式
ad+bc3594 Escort of Dr. Who How
解法：带限制的最短路
枚举出发时间+最短路
3615 Cow Hurdles
解法：Floyd（求任意两点间的最小最高障碍）
3623 Wedding
解法：2-SAT（输出解）
①建矛盾，跑Tarjan。
②判断是否有冲突。
③矛盾标号，opp[ u ] 表示连通分量u的对立矛盾事件所在的分量.
④建反图
⑤拓扑染色。把未染色的点u染成W，并且opp[u]染成B。
⑥输出被染成W的点集。
3653 Here We Go(relians) Again 最短路
3659* Cell Phone Network
解法：树形DP（最小支配集）
sum[u][0] 不覆盖根节点u,儿子全部被覆盖.sum[u][0] += sum[v][1]sum[u][1] u不放,但是覆盖了u节点及所有儿子.sum[u][1] += min( f[v][0],f[v][2] ) f[v][0]至少取一个sum[u][2] 在u放置tower,覆盖该子树.sum[u][2] += min(sum[v][0] , sum[v][1] ,sum[v][2] )
3660 Cow Contest
解法：Floyd ( 传递闭包 )
3662* Telephone Lines
解法：带限制的最短路
dis[i][j]表示到达第i个点用掉j次免费的最小最大边长.
然后spfa转移的时候,多加一个更新：对于u->v的边 , 用掉免费的: 则更新
dis[v][j+1] = min( dis[v][j+1] , dis[u][j] );
3678 Katu Puzzle
解法：2-SAT
3683* Priest John's Busiest Day
解法：2-SAT（输出解）3687 Labeling Balls
解法：差分约束
很神奇的差分约束。。。
dis[b]-dis[a]>=1
dis[i]-dis[0]>=1
因为weight都不相同，所以没有关系的要按照id从小到大赋予不同的weight
[cpp] view
plaincopy
floyd();
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(!g[j][i]) {
addedge(i,j,1);
g[i][j]=1;
for(int k=1;k<=n;k++)
if(g[k][i]) g[k][j]=1;
3692 Kindergarten
题意：N个boy互相认识，M个girl互相认识。其中一些boy和girl互相认识。
要你找最大的集合，使得集合中的人都互相认识。
解法：二分匹配(最大独立集)
求二分图的补图的最大独立集。相当于求剩下的点都互相认识。而边的意义为不认识的人连边。
即去掉最少的点，使得剩下的点互相之间没有边相连。
3694 Network
解法：双连通 + LCA
给定一个连通图后，然后每次加一条边，都要输出当前有几条桥边。
①进行边双连通缩图，缩图后，每条边都为桥边。
②对缩图求LCA，然后对于每次新加边，就将路径上所有的边进行标记。就可以统计剩下还有多少条桥边。
3723 *Conscription
解法：最小生成树转载请保留出处：/web/952.html
上一篇：没有了
读书笔记——“求二进制数中1的个数”(转自http://blog.csdn.net/justpub/article/details/2292823)
本周技术实现排行}