这三题是这场比赛的3道模板题。
1005 即 3986 题，枚举+最短路。
首先求一遍spfa，令ans=dis[n]，并记录最短路径树，延终点到起点枚举（根据pre数组，记点，和mark数组，记邻接表边的编号），每次拆一条边，再做一遍spfa，如果断路则直接输出-1，否则比对当前值与ans的大小。
复杂度上界是O(M * M * C)，C是一个大常数，这是一个俨然达不到的上界。首先最短路径上的边数虽然最坏情况下正比于M，但是这样的话随便拆一条边都应该break，而对于一般情况最短路径上面的边数又是应该远小于M的，所以第一个M，即枚举最短路上的边数，真实的复杂度应该是n。况且，既然题目的数据是随机给出的，最短路上的边数可能是一个很小的数字，因而最终的复杂度可以理解为O(M * K)，K也是一个常数。
表示此题就是不敢写，敢写真是各种水过。
1006 即 3987 题，最小割边数最小。
最大流等于最小割，显然。而想让最小割中的边数最小，即，一个比较简单的想法就是，一条增广路上面只要割一条边就好。
我的做法，按原图建好网络流图之后（无向边什么的怎么处理都是常识哈），对于每条边乘以一个大数（大于总边数）再加1，然后流之，最后maxflow % 大数 即为最小割最少边数的边。
证明，假设第i条增广路的原始流量为xi，那么现在的流量是A*xi+1，A为大数；最后的maxflow，原图为sigma(xi),新图为A*sigma(xi)+B，那么这里的B其实就是增广路条数。输出B即可。所以要把A设置的大一点，以防被B超越。
解题报告的做法是，原图流完最大流后，建新图，把原图的最小割集中的边添到新图中去，容量为1，再流一遍最大流，即为答案。这两种做法本质相同。
1010 即 3991题，最小路径覆盖。
如果做过poj2060题，会发现这两题一模一样。floyd预处理地图，然后把Q个要求拆点，满足约束的点连有向边，做匈牙利，输出Q-ans-1即可。（邻接矩阵的hungary貌似超时？需要邻接表或者hopcroft？）
代码就不贴了。都是模板题，网上都能搜到代码。
模板题神马的，用来增长自信是吗？一如戴牛所说。
å