续。。。。。
现有18/50+
bzoj 1585： [Usaco2009 Mar]Earthquake Damage 2 地震伤害
比较经典的最小割？。。然而一开始还是不会QAQ
和地震伤害1的区别在于这题求的是最少的损坏牧场数目。把牧场拆点，因为要让1和被报告的点不联通，把1归到S集，被报告的点归到T集，就变成求最小割了。
具体建图：
假设点拆成x和x’，x和x‘间连边（就是等下要割的）。被报告的点和1点：容量无穷大（不能割）；其他点容量为1。
原图中相连的边就按照二分图正常姿势，出点连到入点，容量无穷大（路没坏）。
最后就是s连1，被报告的点连t，容量都无穷大
dinic大法好。。
View
bzoj 2200： [Usaco2011 Jan]道路和航线
正解：根据题目，一条航线就是图的一条割边。。 所以先把图中各个联通块单独拿出来，在联通块里跑最短路（这时联通块里没有负权边，就用Dijkstra+堆去求）。再按联通块之间的拓扑顺序把整张图的最短路求出来。
又wa又T一时爽。。一开始是没注意负权边直接上dij，然后是spfa被卡。。。。spfa+slf就可过了= =巧妙的避开了正解（逃。。。
话说spfa好像并不难卡？。。。以后得小心了QAQ
View Code
bzoj 1575： [Usaco2009 Jan]气象牛Baric
正常dp。。。先预处理出sum[i][j]表示s集中选了第i天和第j天时，原序列中第i+1~j-1天的误差值之和。pre[i]表示s集中第一个选了i的话，1~i-1天的误差和。aft[i]表示s集中最后一个是第i天的话i+1~n天的误差和。
f[i][j]表示最后选第i天，总共选了j天的第1~i天的最小误差。初始化f[i][1]=pre[i];
f[i][j]=min{f[k][j-1]+sum[k][i]}，（1<=k<i，2<=j<=n）。如果min{ f[i][j]+aft[i] }<=E的话就可以了
总复杂度O(n^3)。
View Code
bzoj 1755： [Usaco2005 qua]Bank Interest
如题。。就是求算存钱若干年后的本息之和
View Code
bzoj 1774： [Usaco2009 Dec]Toll 过路费
floyd。。http://www.cnblogs.com/czllgzmzl/p/5070943.html
bzoj 1775： [Usaco2009 Dec]Vidgame 电视游戏问题
一开始以为是状压。。。结果发现数据范围是给01背包的= =
ans[i]表示指出i元的最多产出，f[i]表示当前游戏平台内，花i元买游戏的最大产出。初始化f[i]=ans[i-P]（买游戏得先买平台），（P是当前游戏平台的价格）f[i]就是个01背包。
ans[i]=max(ans[i],f[i])。
View Code
bzoj 1696: [Usaco2007 Feb]Building A New Barn新牛舍
中位数。。好吧是平面上的。设奶牛吃草位置为x[],y[]，理想情况下(ansx,ansy)分别是x数组、y数组排序后的中位数。
n为奇数时，最理想的点是唯一的。但如果那个地方已经有奶牛吃草了的话，就尝试下它相邻4个点（这是仅有的可能次优的几个）。
n为偶数时，点(x[n/2],y[n/2])与点(x[n/2+1],y[n/2+1])组成的矩形内的点都是最优的。（x、y已排序）最优点的个数要减去在矩形里吃草的牛的数量。
View Code
bzoj 1916： [Usaco2010 Open]冲浪
dp。按照拓扑顺序来。。f[i][j]表示从i点到n点，途中j次失误的最大愉悦值，val(i,j)表示i到j这条边的愉悦值。
f[i][j]=min{ max{ f[k][j]+val(i,k) }（没失误），min{ f[k][j-1]+val(i,k) }（失误了= =） }，（存在边i-->k）。
View Code
bzoj 1751： [Usaco2005 qua]Lake Counting
如题。。联通块计数。。注意是八连通= =
View Code
bzoj 1914： [Usaco2010 OPen]Triangle Counting 数三角形
极角排序一下。。http://www.cnblogs.com/czllgzmzl/p/5071114.html
bzoj 1590： [Usaco2008 Dec]Secret Message 秘密信息
好久没写trie了。。。注意在trie树上得记录两个信息：在当前节点结束的信息数量；在当前节点还没结束的信息数量。。
每次查找的答案就是 路径上已经结束的数量+最后那个节点上还没结束的信息数量。
View Code
bzoj 1718： [Usaco2006 Jan] Redundant Paths 分离的路径
边双联通分量。。先把边双连通分量缩点，就变成如何使一棵树上两两节点间有多条路可走。。。答案就是（叶子节点数量+1）/2。
求边双连通分量时，记录一下当前点的父亲边，如果low[x]==dfn[x]，那么点x的父亲边就是桥。把桥都从原图中去掉，剩下的就是一坨边双联通分量了。
View Code
bzoj 1693： [Usaco2007 Demo]Asteroids
盯了半天英文题面。。。结果发现双倍经验。同bzoj1741。
View Code
bzoj 1716： [Usaco2006 Dec]The Fewest Coins 找零钱
搜题解的话应该连题目名字一起搜。。因为也是poj3260。
店家找钱一定不超过v_max^2。。。因为这就意味着John多给店主硬币超过了v_max个。。想要让这些硬币无法用v_max的硬币替代掉一部分，则它们不同组合的价值和对v_max取模后都各不相同。。。。总之根据抽屉原理这是不可能的。。。
所以对店家跑个无限背包，对john跑个有限背包就行了。
UPD：。。。。。。。。。。。。。。。。。。。论傻逼不好好想题就跑去看题解的危害性。
根据KPM代码可得。。店家找钱一定不超过v_max。。。其实这也是很显然的？（捂脸。。然而为何我想不到）。。找钱超过v_max肯定有硬币是脑残多给的啊。。。
不过更加不科学的是。。。我数组开大反而快了不少。。。。而且是多次试验确定不是测评姬看脸= =。。。。导演这和说好的不一样。。。
数组开2w+就#1了。。。开1w+就慢了快一倍TAT。。。感人肺腑
View Code
bzoj 2199： [Usaco2011 Jan]奶牛议会
2-SAT问题。。。这类问题似乎没法怎么包装。。。对于每头奶牛，如果它的某票没实现的话，另一票一定要实现。。。
因为有的议案结局未定。。而且数据范围不大。。直接暴力上。。。时间复杂度O(nm)
不知道如果缩点后搞的话怎么处理那些未定的议案TAT
View Code
bzoj 1712： [Usaco2007 China]Summing Sums 加密
矩阵乘法。。。由题目得出，Ci‘=sum-Ci，（sum表示前一轮中奶牛数字和）。本轮结束后sum‘=sum*n-sum。
构造矩阵。。一个n行2列的矩阵A，第i行第一列为Ci，第二列为sum。
第二个矩阵B为2*2的矩阵，第一行为-1,0；第二行为1,(n-1)。
为啥卡了半天常数还是那么慢TAT
View Code
bzoj 1583： [Usaco2009 Mar]Moon Mooing 哞哞叫
首先根据题目给出的式子，两种方式叫声时长都是递增的。。就变成了在两个递增的数列中取出前n小的。。
可以无脑的分别求出两种叫法的前n项再合并。。。。也可以只记录当前两种叫法分别叫到了多长时间，每次选下一次叫时间短的加入答案（因为可以当前项算出后一项时长）。
View Code
bzoj 1731： [Usaco2005 dec]Layout 排队布局
差分约束。。http://www.cnblogs.com/czllgzmzl/p/5072819.html
原文：http://www.cnblogs.com/czllgzmzl/p/5074166.html