if(pre[t] >= 0) {
break; } }
if(pre[t] < 0) {
break; }
aug = 0x7fff;
for(u = pre[v = t]; v != s; (v = u), (u=pre[u])) {
if(c[u][v] < aug) {
aug = c[u][v]; } }
for(u = pre[v = t]; v != s; (v = u), (u = pre[u])) {
c[u][v] -= aug; c[v][u] += aug; }
flow += aug; }
return flow; }
3、 二分图
（1） 含义的理解
二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。 2、相关应用
作为一种数学模型，二分用途是十分有用的，许多问题可以用它来刻划。例如“资源匹配”、“工作安排”、“人员择偶”等等。而这就需要考虑匹配问题。
匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
而二分图最大匹配可以用最大流或者匈牙利算法。 最大流在网络流中有介绍。 匈牙利算法为：（资料：百度百科）
匈牙利算法是由匈牙利数学家Edmonds于1965年提出，因而得名。匈牙利算法是基于Hall
定理（此定理使用于组合问题中。二部图G中的两部分顶点组成的集合分别为X, Y, Z,={X1, X2, X3,X4, .........,Xm} , Y={y1, y2, y3, y4 , .........,yn},G中有一组无公共点的边，一端恰好为组成X的点的充分必要条件是： X中的任意k个点至少与Y中的k个点相邻。（1≤k≤m)）中充分性证明的思想，它是部图匹配最常见的算法，该算法的核心就是寻找增广路径，它是一种用增广路径求二分图最大匹配的算法。 算法的思路：
不停的找增广轨,并增加匹配的个数,增广轨顾名思义是指一条可以使匹配数变多的路径,在匹配问题中,增广轨的表现形式是一条\交错轨\也就是说这条由图的边组成的路径,它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有..最后一条边没有参与匹配,并且始点和终点还没有被选择过.这样交错进行,显然他有奇数条边.那么对于这样一条路径,我们可以将第一条边改为已匹配,第二条边改为未匹配...以此类推.也就是将所有的边进行\反色\容易发现这样修改以后,匹配仍然是合法的,但是匹配数增加了一对.另外,单独的一条连接两个未匹配点的边显然也是交错轨.可以证明,当不能再找到增广轨时,就得到了一个最大匹配.这也就是匈牙利算法的思路. 资料来源：
http://www.nocow.cn/index.php/?????????????3?
求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。
增广路的定义(也称增广轨或交错轨)：若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。（M为一个匹配）
由增广路的定义可以推出下述三个结论：
1. P的路径长度必定为奇数，第一条边和最后一条边都不属于M。 2. P经过取反操作可以得到一个更大的匹配M’。
3. M为G的最大匹配当且仅当不存在相对于M的增广路径。
用增广路求最大匹配(称作匈牙利算法，匈牙利数学家Edmonds于1965年提出) 算法轮廓：
1. 置M为空
2. 找出一条增广路径P，通过取反操作获得更大的匹配M’代替M 3. 重复(2)操作直到找不出增广路径为止 程序清单：
const maxm=200; maxn=200; var i,j,k,m,n:longint;
g:array[1..maxm,1..maxn]of boolean;
y:array[1..maxn]of boolean; lk:array[1..maxn]of longint; function find(x:longint):boolean; var i:longint; begin
for i:=1 to n do
if g[x,i] and (not y[i]) then begin y[i]:=true;
if (lk[i]=0)or find(lk[i]) then begin lk[i]:=x; find:=true; exit; end; end;
find:=false; end;
#include
bool g[201][201]; int n,m,ans; bool b[201]; int link[201];
bool init() {
int _x,_y;
memset(g,0,sizeof(g));
memset(link,0,sizeof(link)); ans=0;
if(scanf(\,&n,&m)==EOF)return false; for(int i=1;i<=n;i++) {
scanf(\,&_x);
for(int j=0;j<_x;j++) {
scanf(\,&_y); g[ i ][_y]=true; } }
return true;
}
bool find(int a) {
for(int i=1;i<=m;i++) {
if(g[a][ i ]==1&&!b[ i ]) {
b[ i ]=true;
if(link[ i ]==0||find(link[ i ])) {
link[ i ]=a; return true; } } }
return false; }
int main() {
while(init()) {
for(int i=1;i<=n;i++) {
memset(b,0,sizeof(b)); if(find(i))ans++; }
printf(\\\n\,ans); } }
每次增广时间为O(E),最多进行O(V)次迭代,时间复杂度为O(VE).
五、动态规划、回溯搜索、分治算法、分支定界等计算机算法
一、动态规划
（http://www.nocow.cn/index.php/??¨???è§????） 1、 含义的理解
动态规划（dynamic programming）是运筹学的一个分支，是求解多阶段决策问题的最优化方法。20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一
