hdu 3491 Thieves 最小割
题意：警察蜀黍知道有一伙犯罪团伙要从S点到达H点。每一个点需要一定的人数镇守。问需要最少的人数截断犯罪团伙从S到H的路使得不能从S到达H。
建图：
拆点。每个点i拆成i->i’和i’->i(因为是双向边)，边权为需要的人数
存在一条u->v的边就这么建u’->v和v’->u(双向边),边权为INF。
代码：
//author: CHC//First Edit Time: 2014-11-17 22:53//Last Edit Time: 2014-11-17 23:26#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits> ...
hdu 3820 Golden Eggs 最小割
题意：有n*m的方格，每个方格可以放金色鸡蛋或者银色鸡蛋，只能放一个，放金色鸡蛋在不同的格子有不同的得分，同理银色鸡蛋也是。如果相邻两个格子是金色鸡蛋的话那么扣除G分，如果相邻两个格子是银色鸡蛋的话扣除S分。问可以放的最高分数是多少
建图：
1)每个格子只能放金色鸡蛋或者银色鸡蛋，也就是说只能二选一，先抓住这个条件观察。
如何才能满足这个条件？
把一个点拆成两个点，一个点代表金色鸡蛋，一个点代表银色鸡蛋。
我们把x拆成x和x’
建图s-x-x’-t，我们令x-x’边权INF，这样割集(s-t)不可能取到x-x’，只能是s-x或者x’-t，并且两者不可能同时在割边集里。
如此一来解决了第一个问题。
这样建图得到的结果是什么？是放的方法中最小的分数。
2)相邻金色鸡蛋的格子扣除G分，相邻银色鸡蛋的格子扣除S分。
这个怎么办？
我们不是已经拆点了吗？
把一个金色鸡蛋和它相邻的其他金色鸡蛋的点连边，边权为G。
但是我们要考虑到有两个集合是怎么分类的。
s-x-y-t。
哪些点属于x集？哪些点属于y集？
首先假设一个点x，拆点为x1和x2
设x1为金色鸡蛋，x2为银色鸡蛋
s->x1 边权 ...
hdu 1569 方格取数(2) 最小割
给n*m的方格，从中取不能相邻的数，使之和最大，输出这个值。
问题其实就是最大点权独立集了。
图G(V,E)中
假设覆盖集为Vx
那么存在(u,v)属于E，那么 u属于Vx或v属于Vx 成立
假设独立集为Vy
那么存在(u,v)属于E，那么 u属于Vy且v属于Vy不成立。
通过德摩根定律可以推出
覆盖集和独立集刚好为补集。。过程自己比划一下就能出来。
代码：
//author: CHC//First Edit Time: 2014-10-31 20:46//Last Edit Time: 2014-11-01 11:21#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include &l ...
hdu 3046 Pleasant sheep and big big wolf 最小割
题意就是问隔绝灰太狼和喜洋洋需要多少栅栏，直接上模板了。
代码：
//author: CHC//First Edit Time: 2014-10-28 22:09//Last Edit Time: 2014-10-28 22:15#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+5;const int MAXM=1e+6;const int INF = numeric_limits<int>::max();const ...
hdu 3657 Game 最小割
题意：给n*m大小的方格，每个方格里有一个数，现在从这些方格里取数，若取走一个方格后有两个相邻的格子没有数就−2(x&y)-2(x \& y)−2(x&y)，取走一个数可以得到那个方格的数，先给定一些方格必须选，然后求最大分数。。
比如：
假设x1,x2,x3已被取走，现在的总分数为s。
那么取走8之后剩余的分数为：s+8−2(8&x1)−2(8&x2)−2(8&x3)s + 8 - 2(8 \& x_1) - 2(8 \& x_2) - 2(8 \& x_3)s+8−2(8&x1)−2(8&x2)−2(8&x3)
思路：
其实这题我没有做出来。。看了别人的建图方式之后，突然有种恍然大悟的感触，但是仔细一想，不对。。我并不知道为什么这样的。我想知道是为什么。所以做了很多猜测和探索。。如果不对请指正。
建图方式：
建立超级源点s和超级汇点t。
横纵坐标之和为偶数的为X集合，横纵坐标为奇数的为Y集合。
s->x
权值为点权，如果这个点必须选，那么就是INF
x->y
权值为2( ...
费用流专题总结
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=56305#overview
A.
模板题
每个小人到每个房子都建一条边，容量为1，权值为小人到房子的距离。
S->每个小人建一条边。
每个房子->T建一条边。
B.
题意是给一个图。这个图中每一个点都一定会属于一个子图，这个子图是哈密顿回路(走过每个点有且仅一次)。
这道题和以前做过的一道网络流题目很相似。。
把点i拆成两个点 i掌管入边 i’掌管出边 如果存在i->j的话就是i’->j
毕竟一个点只有一个出度和一个入度。
S->i
i’->T
跑费用流。完、
C.
题意是给一个无向图。删除某些边后的子图是哈密顿回路(走过每一个点有仅一次)，并且使这个子图的权值最小。
做法同上、不过要注意的是无向图。
D.
题意是给一个有向图。求x个子图(所有子图的点的集合是n)是哈密顿回路的这x个子图的权值之和最小。
做法同B
E.
这题很经典。。给个矩阵，从左上角走到右下角最大值。
可以用dp做。。没想到可以用费用流。不过想一想还是挺合理的。
把它看做 ...
HDU 3947 River Problem 费用流
//author: CHC//First Edit Time: 2014-10-20 10:45//Last Edit Time: 2014-10-21 16:11#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1e+5;const int INF= numeric_limits<int>::max();const LL LL_INF= numeric_limits<LL> ...
HDU 4067 Random Maze 费用流
//author: CHC//First Edit Time: 2014-10-16 10:05//Last Edit Time: 2014-10-16 11:16#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1e+5;const int INF= numeric_limits<int>::max();const LL LL_INF= numeric_limits<LL> ...
HDU 2448 Mining Station on the Sea 费用流
//author: CHC//First Edit Time: 2014-10-12 14:30//Last Edit Time: 2014-10-12 15:03#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1e+6;const int INF= numeric_limits<int>::max();const LL LL_INF= numeric_limits<LL> ...
HDU 3395 Special Fish 费用流
//author: CHC//First Edit Time: 2014-10-11 20:13//Last Edit Time: 2014-10-11 20:39//求最大费用，不要求最大流#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=210;const int MAXM=1e+4;const int INF= numeric_limits<int>::max();const LL LL_INF= numeric_li ...