visited[i] = true; q.push(i); } } }
//可能的增广路不存在了 if(!visited[M-1]) break; int u, min = 0xFFFF;
for(u = M-1; u; u = father[u])//找出权值最小的边 {
if(edge[father[u]][u] < min) min = edge[father[u]][u]; }
//减去最小权值
for(u = M-1; u; u = father[u]) {
//前向弧减去
edge[father[u]][u] -= min; //后向弧加上
//存在圆环,这句话关键 edge[u][father[u]] += min; }
//当前增广路径增加的流 ans += min; } }
int main() {
int s, e, w;
while(cin >> N >> M) {
ans = 0;
memset(edge, 0, sizeof(edge)); for(int i = 0; i cin >> s >> e >> w; edge[s-1][e-1] += w; } Ford_Fulkerson(); cout << ans << endl; } return 0; } 40、 采用最大流算法编写一个二分图的最大匹配算法。 41、 什么是“可证难解性”问题，试举出两个例子。 “可证难解性”问题是不可判定的难解问题和可判定的难解问题的总称，比如货郎担问题，子图同构问题。 42、 P类、NP类、NPC。 P类可以找到一个能在多项式的时间里解决它的算法 用确定型图灵机可以在多项式时间内求解的问题 NP问题是指可以在多项式的时间里验证一个解的问题 ? NP类：用非确定型图灵机可以在多项式时间内求解的问题。 NPC 如果任何NP问题都能通过一个多项式算法转换为某个NP问题，那么这个NP问题就称为NPC问题。 43、 一个问题的“难度”是该问题固有的，试举例说明。 一个问题难解性是问题固有的性质，多项式算法是划分问题的类的标准。如果一个问题是不可用的多项式算法求解的，则该问题是难解的。 如停机问题、平铺问题。 44、 简述DTM、NDTM的工作过程。 DTM的执行过程如下: 1.开始时，将?*中的字符串ω放在从1到?ω?的方格中，其它地方放空格符，控制器处在q0状态。 2.读写头扫描第一个方格中的符号a0，转移函数 σ(q0,a0)= (q1,a1,△)根据事先设计好的σ函数表 将当前状态改变为q1 在当前格中将a0改写为a1 根据△=R,S, L确定读写头向右(R),向左(L) ，或不动(S) (一般为σ(qi,ai) = (qi+1,ai+1,△)) 3.直至当前状态q为qy 或qn,计算停止， 若q= qy,答案是“肯定”,DTM接受ω； 若q= qn,答案是“否定”,DTM拒绝ω。 4.每个步骤即为一步计算。 非确定型单带图另机（NDTM），其结构与DTM基本相同，只是多了一个猜想模块和一个只写头。 NDTM形式地定义为（Q，?，Γ，σ，?，q0 ，Qf） 45、 为什么说，只要两个不同的编码系统是多项式相关的，就不影响算法复杂性 的多项式性。 某问题在e1编码下的算法时间复杂性是多项式T(n)。在e2编码下，算法不变，算法时间复杂性T(P(n))，也是一个多项式。 46、 简述SAT问题和COOK定理。 SAT问题：给定一组布尔变量V和一组由V组成的字句集合C，判定是否存在一组满足C中所有子句的真值赋值。（布尔表达式可满足性问题） 布尔表达式的可满足性问题SAT是NP完全的。 ? Cook证明了在NP类中有一个被称为“可满足性问题”具有如下性质： NP类中的所有其他问题都可以多项式归约到这个问题。 47、 如何证明一个问题是NPC的。已知TSP是NPC的，试证明Hamilton问题也 是NPC的。 先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它（由约化的传递性，则NPC问题定义的第二条也得以满足；至于第一个NPC问题是怎么来的，下文将介绍），这样就可以说它是NPC问题了 同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem，旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为 0，两点不直接相连则令其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。Hamilton回路存在当且仅当TSP问题中存在长为0的回路。 48、 当前计算机的速度越来越高，为什么还要研究时间复杂性更低的算法？ 问题的复杂过程和规模的线性增长导致时耗的增长和空间需求的增长对低效的算法来说是超线性的，绝非计算机的速度和容量的线性增长得来的时耗减少和存储空间的扩大所能抵消的。