文件名称：一个暴力算法-ansi-vita 62-2016 modular power supply standard
文件大小：2.84MB
文件格式：PDF
更新时间：2024-06-29 16:21:26
集训队论文集
3.1 一个暴力算法 根据算法 1，我们现在已经能够判定图 G 是否存在完美匹配了。那么我们可以立刻得 到一个构造匹配的暴力算法：枚举每条边，删去它的两个端点，并判断剩下的图是否存在 完美匹配。 算法 2 A naive matching algorithm 1: M ← ∅ 2: for i← 1 to n do 3: for j← 1 to n do 4: if viv j ∈ E(G)and det Ã(G − {vi, v j}) , 0 then 5: G ← G − {vi, v j} 6: M ← M ∪ {viv j} 7: end if 8: end for 9: end for 10: return M =0 算法 2需要进行 O(n2)次循环，每次循环需要计算一个 O(n)阶的方阵的行列式，因此 5从此，当我们需要计算 Ã(G)的行列式、逆矩阵，或是需要对 Ã(G)消元时，我们指的是将变量随机赋值后在 Fp 下进行相应 的操作。 18