POJ 1815 Friendship
感觉网络流的题目总是莫名奇妙的卡在数组大小上
数组开小，既能WA，又能TLE，也真实神奇……
题意：
给你一张图，让你求出最小割集，并按照字典序输出。
思路：
老套的思路，那些discuss里的奇淫巧计看了一下貌似全都被推翻了……
枚举+最大流，尝试删点，如果流量减少，则为割点。
#include
SPOJ 287 Smart Network Administrator
坑哭了……
先是一个小地方初始化错误，tle了5发，看到下面说数据很多，还尝试开了输入挂……
然后数组开小，WA了n发
题意：
村通网系列。一个村子只有1号家庭有网络，现在有k家用户想要通网，为了网络质量，在一条街道上的每条网络都必须是不同的网线。问最少需要多少掉网线。（差不多就是这样的，颜色什么的就别管了……）
思路：
这道题我看完第一个想法就是二分，但是因为dinic的复杂度问题不是很敢写。搜了一下题解，居然真的是二分……众所周知dinic的复杂度上限为 O(n^2 * m) 如果是稠密图，最高可达 O(n^4) 二分最多9次，除开重新建图，数据最多500组，n最多500，也就是 500^5 ……
然而结果是 0.69 ，我也不知道是什么单位，在spoj刷题是几百年前了…… ，应该是 s 吧。
AC code
#include
ZOJ 2760 How Many Shortest Path
暑假集训第一天，早上看了一下支配树，结果表示完全不会，看不懂……不得不回老本写起了网络流 题意： 给你一个距离矩阵，问你完全不重叠的最短路数目。 思路： 完全不重叠，意为每条边只能走一次，我以网络流建模，对于每条在最短路径内的边的流量设置为1，跑出来的结果即题意所求。这个很自然想得到吧 关键就在于如何判断一条边是否属于最短路径。 这里给出一种比较好的方法，对于一条边 ( u , v ) ，如果 min ( st , u ) + ( u,v ) + min ( v , en ) 等于最短路径长度，那么这条边就属于最短路径 这也是很显然的 注： 如果起点与终点相同，则直接输出inf ，本人英语不好，看了一下题意我还意淫成了 如果存在( st , en ) 就输出inf。 结果我tle了4发…… 因为一直wa我看了一下其他题解，居然有人以自环>=0为理由A不了……我感觉很奇怪。如果自环权值非负，那么正权值自环必定不在最短路径中，而零自环加不加都没有任何影响。 其他的就是代码美丑的问题了。…
POJ 1149 PIGS
本来在学校新搞的vj上挂了一套网络流的题打算大刷特刷，突然发现还有两天就考毛概了……然而我又一点也没看……不得不先把它放下。 是昨天考完开始看这题的……想了大概3个小时，否定了很多想法，然后就没去想了……因为据说是比较经典的构图题，本来还想自己想出来的，结果今天还是没办法去看了题解，顺便发现了个好东西。 网络流建模汇总 不得不说这道题的构图思路真是巧妙，而且我自己的想法与题解的想法真的已经十分接近了…… 十分建议在看题解之前好好思考构图。 题意： 有n个人买猪，总共有m个猪圈，每个人只能去特定的猪圈买猪，按照给定顺序买，在每次购买之后管理员都可以自由调整这位顾客所能购买的猪圈里的剩下的猪，以便使得卖出的猪最多。问最多能卖多少。 思路： 先放可行思路 * 每个顾客分别用一个结点来表示。 * 对于每个猪圈的第一个顾客,从源点向他连一条边,容量就是该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边,则可以把它们合并成一条,容量相加。 * 对于每个猪圈,假设有 n 个顾客打开过它,则对所有整数 i∈[1, n),从该猪圈的第 i 个顾客向第 i + 1 个顾…
HDU 3572 Task Schedule
网络流复习计划第四题，前几天在复习全国公认挂科率最高的数电，所以一直没做题。 扯一个，数电最后没复习好正打算放弃的时候被老友傻炮拉了一把。应该可以过。 题意： 给你很多任务，每个任务都需要一台机器花费给定的时间才能完成，并且限定了每个任务的完成时间区间( 比如说 [a,b] 在第a天开始，在第b天之前完成，包括b)，一台机器一天只能执行一个任务，有多台机器。问你是否能全部完成任务。 思路： 先歪一个……一开始我看到这题想了一下是想贪心做的，结果在写的过程中就自己 否定–更改 了好几次，结果还是没写出来。 实际上这道题是网络流建图的一道经典题，我们让每一个任务作为流量源点，将每个流量源点与其任务时间区间的每个数建边，流量为1，表示你可以在这个区间内其中任意一天使用一台机器，而每台机器将其作为汇点汇入一个超级汇点即可。 他的数据范围最大都只有500，因为要新建流量源点，所以所有节点数量不超过1000。我觉得复杂度还可以啊，但是discuss里面一堆人都说卡时间，过不去……感觉很奇怪，我是1A的，263s，还没有特意去记录点数，懒得优化…… AC code #in…
POJ 2455 Secret Milking Machine
网络流复习计划第三题 传送门
啊，这道题的建图完全是自己想的，虽然花的时间比较长，但是还是算是1A了(交了第一发忘记删了文件输入……)，老实说，A的有点意外呀……
题意：
小气的农场主发现了个大宝贝并把他藏在了n点，他家在1点，总共n个点有若干条路，谨慎的农场主怕自己的宝贝被偷走，于是要从家里出发，结点不重复的走到大宝贝t次。问你在农场主所走的路径中最长的两点距离最短为多少。
思路：
当然还是二分啦！
先是建立距离图。再二分距离，再额外建图，若两点距离小于等于二分值 limit ，则建立双向建边，流量均为 1 。再跑一次dinic，如果总流量大于等于 t ，说明这个limit是满足条件的，我们再尝试缩小它，否则，增大它。
注意： 此题存在重边，存在重边的图，必须用邻接表存储。为什么来着，突然忘了，以后再补
//wordpress的markdown插件有个bug，代码太长的话头文件就显示不了，现在暂时分开……
#include
POJ 2112 Optimal Milking
网络流复习计划第二题 传送门
题意：
一个不负责任的地主有很多奶牛，他让奶牛们自己去产奶机器那里产奶，给你路径矩阵，产奶机器最多同时的奶牛是给定的，要你使走得最远的奶牛距离最短。
思路：
这题建边应该是我到现在写得比较妙的建图了。先是用flyod求出任意两个点的最短距离。(其实我们最主要想求的是每头奶牛与每台机器的最短距离)。然后我们二分这个距离区间，如下建边
1. 对于每头奶牛对于每台机器最短距离小于等于我们的二分值limit ,则建边，流量为 1 。
2. 建立超级源点，使得超级源点到每头牛的流量为 1 。
3. 建立超级汇点，使得每台机器到超级汇点的流量为 m。
每次二分跑一遍dinic，如果流量等于牛的数量，则可以缩短距离。
注： 这道题值得注意的坑点有
* 结点数已改，应该是在1000以上
* 距离矩阵距离为0应该改成inf 给我好好读题呀！！！
* k是机器数，c是奶牛数…… （我就一直wa在这里……
#include
POJ 1459 Power Network
还有半个月不到的时间暑假集训就开始了，这点时间里我准备复习一下网络流，毕竟已经好久没写了……其实也没有写多少
传送门
题意
网络流裸题，题目写的超级烦，简单说就是发电站供电，有很多发电站，用户和线路，问你所有发电站最多同时给用户供多少电。
思路
基础网络流建边，加一个超级源点和超级汇点即可。
#include