网络流经典题
一、最大流：
1、POJ 1273纯最大流
2、Poj1459 这题是标准的最大流问题，经典网络流构图，图已给出，数据规模也很适中，但是比较变态的是读数据。
要去除空格和回车。
3、POJ_2455（相同题型：poj2112 ）二分答案+最大流
思路：二分答案，用权值比二分出来的答案小的边来建图。
网络流判定的是是否能够满足找到t条路径。
4、poj1149 网络流关键在建图，图建好了，什么都解决了
5、poj3281 网络流+拆点
6、poj1637混合图欧拉回路用的是网络流
7、poj 2391 floyd + 二分搜索 + 拆点建图 +网络流
8、poj2699枚举人数+ 最大流---模型转化很重要
9、
二、最小割：
1、poj1815 求源和汇联通度的题，转换过来就是最大流最小割问题
2、POJ 2987 Firing 最小割
3、POJ 3204 最小割
实际上就是求割边，但这个割边必需是一头能被源到达，另一头能被汇到达。
4、POJ 3308 最大流最小割，
解题思路：把伞兵看成边，行列看成节点，转化为了带权二分图最小点覆盖。
三、有上下界网络流：
建议大家做poj2396和zoj2314，再看一下周源的讲义，另两题，看看题解了解一下做法，掌握思路，以后找时间再做。
资料：周源的《一种简易的方法求解流量有上下界的网络中网络流问题》，
1、POJ2396——上下界可行流
2、zoj 2314(无源汇上下界可行流)
3、【SGU 176】有下界的最小流
参考：/2010/07/632.html
4、sgu194 无源汇上下界可行流
参考：/ylfdrib/archive/2010/10/11/1848077.html
四、最小费用流：
1、poj3680 经典费用流问题
2、poj 3422 费用流，数据很水
3、POJ 2516简单的最小费用流问题
4、poj 2135无向图的最小费用流
5、[WC2007]剪刀石头布——费用流经典题
题目描述
在一些一对一游戏的比赛（如下棋、乒乓球和羽毛球的单打）中，我们经常会遇到A胜过B，B胜过C而C又胜过A的有趣情
况，不妨形象的称之为剪刀石头布情况。
有的时候，无聊的人们会津津乐道于统计有多少这样的剪刀石头布情况发生，即有多少对无序三元组(A, B, C)，满足其中的一个人在比赛中赢了另一个人，另一个人赢了第三个人而第三个人又胜过了第一个人。
注意这里无序的意思是说三元组中元素的顺序并不重要，将(A, B, C)、(A, C, B)、(B,A, C)、(B, C, A)、(C, A, B)和(C,B, A)视为相同的情况。
有N个人参加一场这样的游戏的比赛，赛程规定任意两个人之间都要进行一场比赛：这样总共有场比赛。
比赛已经进行了一部分，我们想知道在极端情况下，比赛结束后最多会发生多少剪刀石头布情况。
Your Task
给出已经发生的比赛结果，你可以任意安排剩下的比赛的结果，要求得到尽量多的剪刀石头布情况。
输入文件
输入文件的第1行是一个整数N，表示参加比赛的人数。
之后是一个N行N列的数字矩阵：一共N行，每行N列，数字间用空格隔开。
在第(i+1)行的第j列的数字如果是1，则表示i在已经发生的比赛中赢了j；该数字若是0，则表示在已经发生的比赛中i败于j；该数字是2，表示i和j之间的比赛尚未发生。
数字矩阵对角线上的数字，即第(i+1)行第i列的数字都是0，它们仅仅是占位符号，没有任何意义。
输入文件保证合法，不会发生矛盾，当i≠j时，第(i+1)行第j列和第(j+1)行第i列的两个数字要么都是2，要么一个是0一个是1。
输出文件
一个数字表示在你安排的比赛中，出现了多少剪刀石头布情况。
样例输入
3
0 1 2
0 0 2
2 2 0
样例输出
1
数据约定
30%的数据中，N ≤6；
100%的数据中，N ≤100。
5、图匹配：
Poj 1469、pku 1274 二分图匹配简单题
Poj 3041 二分图最大匹配最小点覆盖=最大匹配
poj3216 最小路径覆盖
Poj 2446二分图的最大匹配。
思路很巧妙
6、差分约束系统
参加：/accplaystation/blog/item/7c6d10136ef28b856438db6b.html 3169 Layout 差分约束
poj1364 King 差分
poj1716 Integer Intervals 及poj1201 Intervals后者是前者的进化版
7、缩环缩点、强连通
3694 Network 无向图缩点
1236 强连通缩点好题
3160 Father Christmas flymouse 强连通去环缩点，重新构图好题
8、欧拉回路
1041 典型欧拉回路题
1780* Code 简单的欧拉回路题
1637 混合图的欧拉回路好题
2230 Watchcow 欧拉回路双向欧拉回路。