5830人阅读
POJ 2449 Remmarguts' Date(中等) &AC
http://acm./JudgeOnline/problem?id=2449
题意：经典问题：K短路
解法：dijkstra+A*(rec)，方法很多
相关：http://acm./JudgeOnline/showcontest?contest_id=1144
该题亦放在搜索推荐题中
POJ 3013 - Big Christmas Tree(基础) &AC
http://acm./JudgeOnline/problem?id=3013
题意：最简单最短路，但此题要过，需要较好的程序速度和，还要注意精度
解法：Dijkstra
POJ 3463 - Sightseeing(中等) &AC
http://acm./JudgeOnline/problem?id=3463
题意：最短路和比最短路大1的路的数量
解法：需要真正理解dijkstra
POJ 3613 - Cow Relays(较难) &AC
http://acm./JudgeOnline/problem?id=3613
题意：求经过N条边的最短路
解法：floyd + 倍增，贪心
POJ 3621 - Sightseeing Cows(中等) &AC
http://acm./JudgeOnline/problem?id=3621
题意：求一个环路，欢乐值 / 总路径最大
解法：参数搜索 + 最短路(ms 原始的bellman tle, 用spfa才过)
POJ 3635 - full tank?(中等) &AC
http://acm./JudgeOnline/problem?id=3635
题意：最短路变形
解法：广搜
相关：/hnu_reason/blog/item/086e3dccfc8cbb.html
生成树问题
基本的生成树就不放上来了
POJ 1639 - Picnic Planning(较难)&AC
http://acm./JudgeOnline/problem?id=1639
题意：顶点度数有限制的最小生成树
解法：贪心 + prim/kruskal
POJ 1679 - The Unique MST(基础) &AC
http://acm./JudgeOnline/problem?id=1679
题意：判断MST是否唯一
解法：prim就行，不过还是易错的题
POJ 2728 - Desert King(中等) &AC
http://acm./JudgeOnline/problem?id=2728
题意：所谓最优比率生成树
解法：参数搜索 + prim
POJ 3164 - Command Network(难)&AC
http://acm./JudgeOnline/problem?id=3164
题意：最小树形图
解法：刘朱算法，这个考到的可能性比较小吧？
POJ 3522 - Slim Span(基础) &AC
http://acm./JudgeOnline/problem?id=3522
题意：求一颗生成树，让最大边最小边差值最小
解法：kruskal活用
连通性，度数，拓扑问题
此类问题主要牵扯到DFS，缩点等技巧
POJ 1236 - Network of Schools(基础) &AC
http://acm./JudgeOnline/problem?id=1236
题意：问添加多少边可成为完全连通图
解法：缩点，看度数
POJ 1659 - Frogs' Neighborhood(基础)&AC
http://acm./JudgeOnline/problem?id=1659
题意：根据度序列构造图
解法：贪心，详细证明参见havel定理
POJ 2553 - The Bottom of a Graph(基础) &AC &（好题）
http://acm./JudgeOnline/problem?id=2553
出度为0的强连通分量的所有的点
POJ 2186 - Popular Cows(基础)&&AC &（好题）
http://acm./JudgeOnline/problem?id=2186
题意：强连通分量缩点图出度为0的点
POJ 2762 - Going from u to v or from v to u?(中等)&AC
http://acm./JudgeOnline/problem?id=2762
题意：单向连通图判定
解法：缩点 + dp找最长链 (我是用 缩点+ 欧拉路判断，最后证明这方法是错的)
POJ 2914 - Minimum Cut(难)&AC &（难）
http://acm./JudgeOnline/problem?id=2914
题意：无向图最小割
解法：Stoer-Wagner算法，用网络流加枚举判定会挂
POJ 2942 - Knights of the Round Table(难)&AC
http://acm./JudgeOnline/problem?id=2942
题意：求双联通分量(或称块)中是否含奇圈
解法：求出双连通分量后做黑白染色进行二分图图判定
相关：/zfy0701/blog/item/57ada7ed104ce9d2b31cb104.html
POJ 3177 - Redundant Paths(中等)&AC
http://acm./JudgeOnline/problem?id=3177&（和3352一样）
题意：添加多少条边可成为双向连通图（任意两点间有两条不共边的路径）
解法：把割边分开的不同分量缩点构树，看入度
公式： 入度为1的leaf个数， ( leaf + 1 ) / 2
POJ 3352 - Road Construction(中等)&AC
http://acm./JudgeOnline/problem?id=3352&（和3177一样）
题意：添加多少条边可成为双向连通图（当删除任意一条边的时候，图还保持连通性）
解法：把割边分开的不同分量缩点构树，看入度&( leaf + 1 ) / 2
建议对比下1236，有向图添加多少条边变成强连通图
POJ 3249 - Test for Job(基础)
http://acm./JudgeOnline/problem?id=3249
解法：bfs / dfs + dp
POJ 3592 - Instantaneous Transference(基础)&AC
http://acm./JudgeOnline/problem?id=3592
解法：缩点，最长路，少人做的水题，注意细节 （和 3160 类似）
POJ 3687 - Labeling Balls(中等) &AC &（莫名其妙，有空再重新看）
http://acm./JudgeOnline/problem?id=3687
解法：拓扑排序
POJ 3694 - Network(中等)&AC
http://acm./JudgeOnline/problem?id=3694
解法：双连通分量+并查集
此类问题理解合取式的含义就不难
POJ 2723 - Get Luffy Out(中等)&AC （好题）
http://acm./JudgeOnline/problem?id=2723
解法：二分 + 2-SAT判定
POJ 2749 - Building roads(较难)&AC
http://acm./JudgeOnline/problem?id=2749
解法：二分 + 2-SAT判定
POJ 3207 - Ikki's Story IV - Panda's Trick(基础)&AC
http://acm./JudgeOnline/problem?id=3207
解法：简单的2-sat，不过其他方法更快
POJ 3648- Wedding(中等)&AC
http://acm./JudgeOnline/problem?id=3648
解法：用2-sat做会比较有意思，但是暴搜照样0ms
POJ 3678 - Katu Puzzle(基础)&AC&
http://acm./JudgeOnline/problem?id=3678
解法：直接按合取式构图验证就行了（本质）
POJ 3683 - Priest John's Busiest Day(中等)&AC
http://acm./JudgeOnline/problem?id=3683
解法：n^2枚举点之间的相容性构图，求解2-SAT (要求输出方案)
POJ 2296&Map Labeler&(中等) (第七道)AC
& & & & http://poj.org/problem?id=2296&
&& & & &解法：上下边形成2元关系。然后构完图，求2-SAT
POJ 3905&Perfect Election(中等) (第八道)&AC
&& & & &http://poj.org/problem?id=3905（好题！）
&& & & &解法: 建好矛盾，直接就是2-SAT
最大流问题
变形很多，最小割最大流定理的理解是关键
POJ 1149 - PIGS(较难)&AC &（灰常好题！强烈推荐）
http://acm./JudgeOnline/problem?id=1149
绝对经典的构图题
POJ 1273 - Drainage Ditches(基础)&AC
http://acm./JudgeOnline/problem?id=1273
最大流入门
POJ 1459 - Power Network(基础)&AC
http://acm./JudgeOnline/problem?id=1459
POJ 1637 - Sightseeing tour(Crazy)&AC
http://acm./JudgeOnline/problem?id=1637
题意：求混合图的欧拉迹是否存在
解法：无向边任意定向，构图，详建黑书P324
POJ 1815 - Friendship(中等)&AC
http://acm./JudgeOnline/problem?i1d=815
题意：求最小点割
解法：拆点转换为边割
相关：/zfy0701/blog/item/a521f230b06dea9fa9018e0e.html
POJ 1966 - Cable TV Network(中等)&AC
http://acm./JudgeOnline/problem?id=1966
题意：去掉多少点让图不连通
解法：任定一源点，枚举汇点求点割集(转换到求边割)，求其中最小的点割
POJ 2112 - Optimal Milking(基础)&AC &（好题）
http://acm./JudgeOnline/problem?id=2112
二分枚举，最大流
POJ 2391 - Ombrophobic Bovines(中等)&AC &（好题）
http://acm./JudgeOnline/problem?id=2391
题意：floyd, 拆点，二分枚举
相关：/zfy0701/blog/item/3ef0eaf8226acff.html
POJ 2396 - Budget(中等)
http://acm./JudgeOnline/problem?id=2396
题意：有源汇的上下界可行流
解法：用矩阵-网络流模型构图，然后拆边
相关：/zfy0701/blog/item/e15e3e5343c1ba.html
最小割模型在竞赛中的应用
POJ 2455 - Secret Milking Machine(基础)&AC & （好题）
http://acm./JudgeOnline/problem?id=2455
二分枚举，一般来说需要写对边容量的更新操作而不是每次全部重新构图
POJ 2699 - The Maximum Number of Strong Kings(较难)
http://acm./JudgeOnline/problem?id=2699
解法：枚举人数 + 最大流(感谢xpcnq_71大牛的建图的提示)
POJ 2987 - Firing(较难)&&AC &（经典）
http://acm./JudgeOnline/problem?id=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.do?problemCode=2071
也是此类型，最大权闭包图。 多加了输出 买哪些组件，使效益最大。
POJ 3084 - Panic Room(中等，好题)
http://acm./JudgeOnline/problem?id=3084
解法：根据最小割建模
POJ 3155 - Hard Life(很挑战一题)&AC &（难）
http://acm./JudgeOnline/problem?id=3155
题意：最大密度子图
解法：参数搜索 + 最大权闭合图，A.V.Goldberg的论文(nb解法)
最小割模型在信息学竞赛中的应用 一文中也有讲
POJ 3189 - Steady Cow Assignment(中等)&AC
http://acm./JudgeOnline/problem?id=3189
题意：寻找最小的区间完成匹配
解法：这题充分说明SAP的强大，纯暴力可过。更好的方法是在枚举区间的过程中不断删边和加边继续网络流过程
POJ 3204 - Ikki's Story I - Road Reconstruction(基础)
http://acm./JudgeOnline/problem?id=3204
ZOJ 2532 - Internship(基础)
http://acm./onlinejudge/showProblem.do?problemCode=2532
题意：确定边是否是某个割中的边
解法：两边dfs求割, 或暴力枚举(需要写取消某条增广路的操作(但数据弱，也许不取消也能混过))
POJ 3308 - Paratroopers(较难)
http://acm./JudgeOnline/problem?id=3308
POJ 2125 - Destroying The Graph(难)
http://acm./JudgeOnline/problem?id=2125
题意：最小点权覆盖
POJ 3469 - Dual Core CPU(中等)
http://acm./JudgeOnline/problem?id=3469
题意：最小割
POJ 3498 - March of the Penguins(中等)
http://acm./JudgeOnline/problem?id=3498
题意：满足点容量限制的网络流
解法：拆点把点容量转换为边容量，枚举汇点
ZOJ 2587 - Unique Attack(较难)
http://acm./show_problem.php?pid=2587
题意：确定最小割是否是唯一的
解法：得理解dfs求最小割算法的本质
SPOJ 839 - Optimal Marks(难)
http://www.spoj.pl/problems/OPTM/
解法：很经典哦，见amber的集训队论文，根据标号的每一位求最小割
SGU 326 - Perspective(中等)
http://acm.sgu.ru/problem.php?c0&problem=326
比较经典的构图法
费用流问题
可以KM解的就不放在这里，另外，感觉除非很特殊的图，一般用连续增广路的算法就够了
POJ 2175 - Evacuation Plan(中等)
http://acm./JudgeOnline/problem?id=2175
题意：判断是否给定解是最优解，比较阴的一题
解法：根据给出的计划构造流，然后消且只消一次负圈
POJ 3422 - Kaka's Matrix Travels(中等)
http://acm./JudgeOnline/problem?id=3422
解法：拆点
POJ 3680 - Intervals(较难)
http://acm./JudgeOnline/problem?id=3680
题意：略，这题还是蛮经典
解法：discuss中比较详细
SPOJ 371 - Boxes(简单)
http://www.spoj.pl/problems/BOXES/
解法：费用流，但似乎有比网络流更好的做法
SGU 185 - Two shortest(中等)
http://acm.sgu.ru/problem.php?c0&problem=185
题意：求两条不想交的最短路径
解法：费用流，也可以最短路 + 最大流。
正确理解KM算法是很重要的
这里我还要说几句：最正确解最小权匹配的办法是用一个很大的数-当前边权值，而不是直接对边权取反(这样只能处理左右点相等的完全二分图，即K(n, n)
以上有可能还是说的有点问题，以后补充
POJ 1486 - Sorting Slides(中等)&AC
http://acm./JudgeOnline/problem?id=1486
题意：二分图的必须边
解法：需正真理解最大匹配算法，详见/kevin0602/blog/item/1d5be63b5bec9bec14cecb44.html
POJ 1904 - King's Quest(中等，好题)&AC
http://acm./JudgeOnline/problem?id=1904
题意：求二分图所有可能的匹配边
解法：虽然最终不是用匹配算法，但需要理解匹配的思想转换成强连通分量问题。
POJ 2060 -Taxi Cab Scheme(基础)&AC
http://acm./JudgeOnline/problem?id=2060
题意：最小路径覆盖
POJ 2594 -Treasure Exploration(中等)&AC
http://acm./JudgeOnline/problem?id=2594
题意：可相交最小路径覆盖
解法：先传递闭包转化下
POJ 3041 - Asteroids(基础)&AC
http://acm./JudgeOnline/problem?id=3041
解法: 简单行列匹配&
POJ 2226 - Muddy Fields(基础)&AC
http://acm./JudgeOnline/problem?id=2226
题意：行列的覆盖
解法：最小点集覆盖 = 最大匹配
POJ 2195 - Going Home(基础)&AC
http://acm./JudgeOnline/problem?id=2195
题意：最小权值匹配
解法：KM算法
POJ 2400 - Supervisor, Supervisee(中等)&AC
http://acm./JudgeOnline/problem?id=2400
题意：输出所有最小权匹配
解法：KM, 然后回溯解，汗，输入的两个矩阵居然是反过来的
POJ 2516 -Minimum Cost(中等)&AC
http://acm./JudgeOnline/problem?id=2516
题意：最小权值匹配或最小费用流
解法：拆点 + KM算法(只有正确的才能过)，费用流(ms错的可能也能过)
POJ 3686 - The Windy's(较难)&AC
http://acm./JudgeOnline/problem?id=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.php?c0&problem=206
解法：经典题目，也可以使用spoj 412那题的优化
一般是搜索或dp解的
POJ 1419 - Graph Coloring(基础)
http://acm./JudgeOnline/problem?id=1419
题意：图的着色
解法：搜索，可惜题目的数据真是太弱了
POJ 2989 - All Friends(难)
http://acm./JudgeOnline/problem?id=2989
题意：极大团数量
解法：开始狂tle, 后来找了论文：Finding All Cliques of an Undirected Graph（Coen Bron & Joep Kerboscht）
ZOJ 1492 - Maximum Clique(基础)&AC
http://acm./show_problem.php?pid=1492
题意：图的最大团
解法：搜索，如果要求速度，可参考下相应论文
不能成大类的
POJ 1470 - Closest Common Ancestors(基础)
http://acm./JudgeOnline/problem?id=1470
题意：LCA问题
解法：tarjan或RMQ，另外输入很恶心
POJ 1985 - Cow Marathon(基础)
http://acm./JudgeOnline/problem?id=1985
题意：树上的最长路径
POJ 1986 - Distance Queries(中等)
http://acm./JudgeOnline/problem?id=1986
解法：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算法算出每个顶点间的最短距离,然后就是穷举每个顶点。
&& & &使每个俱乐部的成员到(所在村庄)达该顶点的距离之和最小
&& & &村庄到区域的距离即：将村庄作为点的区域(顶点)到枚举顶点的距离
<span style="color:#01 Intervals
解法：差分约束
& & &约束条件：s[b]-s[a-1] &= c &，&0
&= s[i&#43;1]-s[i] &= 1
<span style="color:#36* Network of Schools&
题意：问添加多少边可成为完全连通图
解法：基础强联通
&& & & & & &缩点，看度数
<span style="color:#51 Jungle Roads
解法：基础最小生成树
<span style="color:#73 Drainage Ditches
解法：基础最大流
&& & & & &注意输入时先输边数n，再是点数m
<span style="color:#74 The Perfect Stall
题意：牛和挤奶器最大匹配
解法：基础二分匹配
<span style="color:#75* Cashier Employment &(神题)
解法：差分约束
& & & & &ti[i] 表示从 i 开始工作的人数 ，s[i] &表示 0-i 总共雇佣了多少人 ，&r[i]
&表示 i 所需的至少人数
&& & & & & &ti[i-7]&#43;ti[i-6]&#43;...ti[i]
&= r[i] & ( 表示前8小时开始工作的人数 )
&& & & & & &设：s[i]-s[i-8]
= ti[i-7]&#43;ti[i-6]&#43;...ti[i]
&& & & & & &0 &= S[i]-S[i-1]
&& & & & & 约束条件：①S[i]-S[i-1]
&= 0 &②S[i-1]-S[i] &= -ti[i]
& & & & & & & & & & & & & & ③S[i]-S[i-8] &= r[i] ( i&=8 ) &④S[23]&#43;S[a]-S[a&#43;16] &= r[i] ( i&=7 ) &==&&S[a]-S[a&#43;16]
&= r[i]-S[23]
&& & & & & &
& & & & & & & & & ⑤*注意：S[24]-S[0]&=mid &//这句话要记得
<span style="color:#25 Machine Schedule
解法：&二分匹配(最小点覆盖)
&& & & & & &最小点覆盖：选取最少的点数，使这些点和所有的边都有关联（选择最少的点覆盖所有的边）
解法：差分约束
& & & &&gt：&s[a&#43;b]-s[a-1]&c
&==& &s[a&#43;b]-s[a-1]&=c&#43;1
&& & & & & &lt：&s[a&#43;b]-s[a-1]&c&==&
&s[a-1]-s[a&#43;b]&(-c)
&& & & & & &超级源点：&s[i]-s[n&#43;1] &= 0
<span style="color:#22 Air Raid
解法：二分匹配 (最小路径覆盖)
&& & & & &（伞兵）&最小路径覆盖：用最少的不相交简单路径覆盖所有结点。&
&& & & & &有向图：ans
= n - match() ， 无向图： ans = n - ( match() &#43;1 ) / 2
<span style="color:#59 Power Network&
解法：基础网络流
<span style="color:#66 Girls and Boys
解法：二分匹配&(
最大独立集 )&
&& & & & &
&最大独立集 = 顶点数 - 最小点覆盖
&& & & & & &由于最小点覆盖所有边，所以去掉这些点后，剩下的点之间就没有关联边，即互相独立
1469 COURSES &(HDU1083)
解法：二分匹配(完全匹配
<span style="color:#02 MPI Maelstrom
题意：计算从1发送信息到其他n-1个点最短时间 , 并且信息是同时发出去的
解法：最短路
&& & & & & &计算1到其他n-1个点的最短时间，再取最大即可(因为信息是同时发的)
1511* Invitation Cards (HDU1535)
解法：最短路
&& & & & & &来回最短路(单向):&&正向建边 , 可以计算出S到任意点的最短路。
&& & & & & & & & & & & & & & & & & & & & & & & &反向建边,那么S到任意点的最短路就相当于从任意点回来S的最短路
1548 Robots
解法：二分匹配(有向无环图的最小路径覆盖)
1566 The Doors
解法：计算几何&#43;最短路
1637* Sightseeing tour&
解法：混合欧拉回路
& & & & &单向边：无用，删 &in[b]&#43;&#43; ; out[a]&#43;&#43;
&& & & & & &双向边：随意定向
&in[b]&#43;&#43; ; out[a]&#43;&#43;
&& & & & &【建图】x
= in[i]-out[i]&
&& & & & & & & & & & & & & ①如果x是奇数，肯定不存在欧拉回路
&& & & & & & & & & & & & & ②如果x&0 (入&出) 连 i -& T &容量： x/2
&& & & & & & & & & & & & & ③如果x&0 (入&出) 连 S -& i &容量：-x/2 &
&& & & &【判断】是否满流
<span style="color:#98&Alice's Chance
题意：有N个film，Alice想要参加所以film的主演。
给出每个film在每个星期的开拍时间，和需要拍的天数，并且给出期限日期。
问Alice是否能合理安排时间，完成所有的film的拍摄工作。
解法：多重匹配
X部为:7*50天,Y部为每个film.容量为需要的天数D[i] .
建边:对于每个film,从第一个星期开始每个星期的可以拍的时间和Y部连一条边.一直到期限日期那一个星期结束连边.然后求一次多重匹配.判断是否是完美匹配.
<span style="color:#16 Integer Intervals&
题意：和1201一样
解法：差分约束
&& & & & &&&&① s[b&#43;1]-s[a]&=2
&&② 0 &= s[i&#43;1]-s[i] &= 1&
&& & & & & & ③&s[i]&=0
(第③个是建超级源点的条件，这里可以不要)
1719&Shooting Contest
题意：有r行c列的矩阵。每一列都有2个白&#26684;子。现在要求你射击c次，使得每一列都被射击正好一次。并且每一行至少都射击一次。
求是否有解，并输出每一列射击的相应行坐标。
解法：二分匹配（行列匹配）
X部为行，Y部为列。先进行一次行列匹配。判断是否match() == r 。如果是，说明每一行都对应了一列。那么剩下的未匹配的列，进行随意行跟它匹配即可。这样就可以使得每一行都没匹配过，并且每一列都仅被匹配了一次。
1724* ROADS&
解法：带限制的最短路
&& & & & & 方法① &将每个点拆分，开二维 dis[ i ][ j ] 记录。表示到达节点
总共花费 j 的金钱所需的最短路 ( j&=K )
&& & & & & 方法②广搜bfs()
&#43; 优先队列
1734&Sightseeing trip
&& & & & & & 解法：Floyd
求最小环 &#43; 输出路径
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;i&k;i++) if(e[i][k]!=inf)
for(j=1;j&i;j++) if(e[k][j]!=inf) {
if(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];
<span style="color:#80* Code &（好题）
题意：要求所有的n位数编码成一个数字串，每个n位数只出现一次
解法：欧拉回路
可以把n位数看成边，那么可以把它的前n-1位看成点A，后n-1一位看成点B，
那么它就是A-&B的一条边。找一次欧拉回路就行了。
此题要用栈模拟递归函数！！！
1789 Truck History
解法：最小生成树(
prim 或 kruskal)
1797 Heavy Transportation&
解法：最小生成树 或 最短路 或 dfs
&& & & & & &二分枚举下限，用最小生成树 或 最短路 或 dfs 判断 1 和 n 是否连通
解法：简单最短路
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&
解法：二分&#43;网络流
&& & & & &二分最远距离，建可行边，判断是否符合要求
2125 Destroying The Graph
解法：最小割(最小点权覆盖)
最小点权覆盖：最小点权覆盖所有的边 （等同于最大独立集）
拆点并将点权转成边权。
i 和 i&#43;n 分别表示出入，S 连 i 删出边的权， i&#43;n 连 T 删入边的权。 求最小割。
2135 Farm Tour
题意：无向图，从起点到终点，再从终点到起点。不能走重复的边。求最短路程。
解法：费用流
相当于找两条从起点到终点不重复的路径。
S 连起点，容量2 费用0 ，&&终点连 T，容量2 费用0
连 j ，j 连 i 容量1 ， 费用边权w
2139 Six Degrees of Cowvin Bacon
题意： &类&#20284; HDU1869 六度分离
这里求的是以哪个人 i 为中心，到其他人的分离度的平均&#20540;最小，求最小&#20540;
解法：&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
解法：二分&#43;最短路
2267* From Dusk till Dawn or: Vladimir the Vampire 最短路
2289 Jamie's Contact Groups &(HDU1669)
解法：二分&#43;二分图多重匹配 (或 二分答案&#43;网络流)
2296&Map Labeler&
解法：2-Sat (二分枚举答案)
2312 Battle City
题意：给以图,坦克能不能走到目标位置.
解法：上下左右连边，然后最短路一下就可以了(或者直接用BFS)
2337 Catenyms
解法：欧拉路径
①用并查集判断连通性
②判断入度和出度是否满足
&& &欧拉回路-& 入度=出度
&& &欧拉路径-& 只有一个,入度-出度=1 ; 只有一个,出度-入度=1
2349 Arctic Network
题意： 有卫星电台的城市之间可以任意联络。没有卫星电台的城市只能和距离小于等于D的城市联络。题目告诉你卫星电台的个数S，让你求最小的D.
做最小生成树，去掉最长的S条边后，剩下最长的边就是D.
也就是求最小生成树中第S&#43;1长的边。
解法：最小生成树
2353 Frogger
解法：最短路(或最小生成树)
2367 Genealogical tree
解法：基础拓扑排序
2387 Til the Cows Come Home
解法：基础最短路
2391* Ombrophobic Bovines
解法：二分&#43;网络流
S 连 i (牛) &容量: 牛的数量
i&#43;n (棚) 连 T 容量: 能hold牛的个数
i 连 j&#43;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
解法：二分&#43;网络流
注意重边也要！
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
解法：最短路预处理&#43;位运算&( 好题啊! )
2584 T-Shirt Gumbo
解法：多重匹配
2594* Treasure Exploration
解法：floyd传递性&#43;二分匹配(最小路径覆盖)
2672 Hotkeys
2723 Get Luffy Out
解法：二分&#43;2-Sat
2-Sat的本质就是：一件物品选了，对另一件物品的影响。
每个物品有2个状态： 选，不选 。即 x 和 ~x
如 x y 。选了x，y钥匙就会消失。那么选了x就不能选y， 即选了x就选 ~y (非y)
2724 Purifying Machine 2分匹配
2728 Desert King 最优比例生成树
<span style="color:#49* Building roads (好题!)
解法：二分&#43;2-Sat
建矛盾: hate的必须分开,&
& like的必须栓在同一个点
&距离矛盾：① dis1[ i ] &#43; dis1[ j ] & mid
& & & & & & & & & & & &②&dis2[ i ] &#43; dis2[ j ] & mid
& & & & & & & & & & & &③&dis1[ i ] &#43; dis2[ j ] &#43; dis & mid
& & & & & & & & & & & &④&dis2[ i ] &#43; dis1[ j ] &#43; dis & mid
记：dis1 表示 cow 到 s1 的距离 ， dis2 表示 cow 到 s2 的距离 ， dis 表示 s1 到 s2 的距离。
2762 Going from u to v or from v to u?&
解法：强连通&#43;拓扑
强连通缩点，同一分量的不需要考虑了。
不属于同一强连通分支的点就用拓扑排序来判断，如果某次删除点的时候发现两个入度为0的点，则说明这两个点只能由已经被删掉的点到达。
也就是说这两个点互相不可达。所以只要同时出现了多于一个的0入度的点，那么这个图一定是不符合题目要求的，输出&No&.
注：用欧拉路径判断是错的，以下数据
1 2 &&1 3 &&1 5 &&2 4 &&2 5 &&3 4 &&5 3 &&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() ) &#43; match() ;
3037 Skiing&
解法：带限制的最短路 ( 或者 BFS&#43;优先队列 )
由于速度变化过程中，最小为-50倍，最大为50倍。
所以，dis[N][D]开二维，表示到达第i个点，速度变为（D-50）倍的最短时间。
然后直接最短路或者BFS搞之。
3041 Asteroids&
解法：二分匹配
3072* Robot
解法:计算几何&#43;最短路
dis[ u ][ v ] 表示从u到v的状态下，最短时间。
转移 &dis[ u ][ v ] = min( dis[ u ] [ v ] , dis[ j ] [u ] &#43; w &#43; turn( p[j] , p[u] , p[u]
, p[v] ) ) ; { 1&=j&=n }
p[j] , p[u] , p[u] , p[v] ) 用来计算向量 p[j]p[u] 和向量 p[u]p[v] 的夹角。
3114&Countries in War&
解法：强联通&#43;最短路
3159 Candies
解法：差分约束
dis[i]表示第i个kid拿到的糖果数。dis[b]-dis[a]&=c ，求dis[n]-dis[1]的最大&#20540;。 addedge(a,b,c)
(spfa过不了...要用dijkstra&#43;优先队列(什么堆优化的都可以)才可以...)
3160 Father Christmas flymouse&
解法：强联通&#43;最长路
3164 Command Network&
解法：最小树形图（有根树）
3169 Layout
题意：N只牛按顺序从左到右站成一排；
并且 牛a喜欢牛b，那么他们之间的距离不能超过d；
牛a不喜欢牛b，那么他们之间的距离至少要d。
解法：差分约束
& &0&=dis[b]-dis[a]&=c
& &==& dis[b]-dis[a]&=c
& &==& dis[a]-dis[b]&=0
& &dis[b]-dis[a]&=c
& &==& dis[a]-dis[b]&=-c
& &dis[i&#43;1]-dis[i]&=0
& &==& dis[i]-dis[i&#43;1]&=0
3177 Redundant Paths&
解法：边双连通分量
至少要加多少条边，使得图中没有桥边
边双连通缩图之后，叶子结点leaf。那么至少需要加 (leaf&#43;1) / 2 条边，才能使得每条边都至少属于一个环，即没有桥边。
3189 Steady Cow Assignment
题意：有N头牛，B个棚。每头牛对每个棚有个偏好（第一偏好，第二偏好。。。），并且每个棚有一定的容纳量。
现在要你安排牛到每个棚中，使得 牛的最大偏好那个和最小偏好的牛的差&#20540;最小。
解法：枚举偏好区间&#43;多重匹配
枚举偏好&#20540;[ l , r ] , 然后对每个牛偏好在 l ~ r 对应的棚进行多重匹配判断是否完美匹配。然后取最小差&#20540;即可。
3204 Ikki's Story I - Road Reconstruction 最大流
3207 Ikki's Story IV - Panda's Trick
解法：2-SAT
3216 Repairing Company
解法：二分匹配&#43;最短路
3228 Gold Transportation 网络流
3255 Roadblocks&
解法：最短路&#43;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&#43;状压DP
//dp[i][j]
:表示状态i,到达j点的最短路时间
:表示缩图后的u-&v的最短距离
:保存经过1~n的点后回到原点0的最短路
int state=(1&&n);
for(i=0;i&i++) {
for(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
解法：二分&#43;二分匹配
3352 Road Construction
解法：边双连通分量
至少要加多少条边，使得图中没有桥边
边双连通缩图之后，叶子结点leaf。那么至少需要加 (leaf&#43;1) / 2 条边，才能使得每条边都至少属于一个环，即没有桥边。
3439 Server Relocation
解法：最短路
3463 Sightseeing
解法：最短路
Dijkstra求最短路和次短路条数。
3469 Dual Core CPU 最小割&
3487 The Stable Marriage Problem
解法：稳定婚姻
3521&Geometric Map 计算几何&#43;最短路
3522 Slim Span 最小生成树
解法：最小生成树
MST的最大，最小边差&#20540;最小
枚举最小边，然后求MST，保存最小差&#20540;。
3549 GSM phone 计算几何&#43;最短路
题意：给定2*N个点的坐标，让你用前N个点和后N个点一一配对，使得相连的边没有相交的。
解法：KM匹配
首先有一个性质必须知道，那就是最短的配对，必然是没有相交的。于是我们就可以构建二分图，求最小权匹配。
根据三角形不等式
ad&#43;bc&ac&#43;bd & &dc&#43;ab&ac&#43;bd
因此，我们只需要构造二分图，求最小权和匹配
3594 Escort of Dr. Who How&
解法：带限制的最短路
枚举出发时间&#43;最短路
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（最小支配集）
3660 Cow Contest
解法：Floyd ( 传递闭包 )
3662* Telephone Lines
解法：带限制的最短路
dis[i][j]表示到达第i个点用掉j次免费的最小最大边长.
然后spfa转移的时候,多加一个更新：对于u-&v的边 , 用掉免费的: 则更新&
dis[v][j&#43;1] = min(&dis[v][j&#43;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
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
解法：双连通 &#43;&LCA
给定一个连通图后，然后每次加一条边，都要输出当前有几条桥边。
①进行边双连通缩图，缩图后，每条边都为桥边。
②对缩图求LCA，然后对于每次新加边，就将路径上所有的边进行标记。就可以统计剩下还有多少条桥边。
3723 *Conscription
解法：最小生成树
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：186394次
积分：2422
积分：2422
排名：第10918名
原创：44篇
转载：22篇
评论：105条
(1)(1)(4)(6)(10)(1)(1)(3)(1)(2)(1)(1)(7)(1)(2)(24)