首先, 如果一个可行顶标使得原图的相等子图中存在完美匹配 - Read.PDF

首先, 如果一个可行顶标使得原图的相等子图中存在完美匹配, 那么这个完美匹配一定 是最优解. 然后只要证一定存在一组可行顶标, 使得原图的相等子图中存在完美匹配. 只须证: 可以通过改进可行顶标使相等子图中存在完美匹配. 如果现在的相等子图中不存在完美匹配且无增广路, 则匈牙利树中的节点可以分为 4 类. S, T, S , T . 那么在相等子图中, T 中一定存在未盖点, T 到 S 中无匹配边, S 到 T 中无边. 我们现在考虑如何使相等子图产生一条增广路. 方法是: 向匈牙利树中加点. 因为一旦加入, 在未找到增广路前, 不会删掉, 那么不再匈牙利树中 的点的数目在严格减小, 一定有一次加入了那个未盖点, 增广路就找到了. 那么如何加点呢? 用 T 加 S 中的? 无匹配边啊! 用 S 加 T 中的! 怎么改? 一定是 dec(l(x), d) (x ∈S) d min{l(x) +l(y ) −w(x , y ) | x ∈S, y ∈T } 使加一条 从 S 到 T 的边, 也保证 S 到 T 的顶标可行. 为了保证 S 到 T 的顶标可行, 且匹配边不作改变, inc(l(y ), d) (y ∈T) 由于增加了T 的顶标, 所以 S 到 T 的顶标可行. 这样修改后是否会导致有些匹配边不再是匹配边呢? 不会, 因为匹配边只出现在 S 到 T, S 到 T , 而他们的 l(x) +l(y ) 不变. 这样, 尝试从X 中的一个未盖点k 找到增广路, 至多改 n 次可行顶标(每次至少增加 1 个 Y 中的点到匈牙利树中), 为了保证总时间复杂度为 O(n3), 必须使找d 的时间复杂度降到O(n). 为此, 我们定以 slack(y ) = min{l(x) + l(y ) −w(x , y ) | x ∈S}, y ∈T . 在扩展匈牙利树的时候更 新, 在修改可行顶标前, d min{slack(y ) | y ∈T }, 修改以后, 只需要 dec(slack(y ), d)就行了. 总的时间复杂度如何呢? 第k 次要找到从k 出发的一条增广路. 找的全程中, 扩展匈牙利 树是 O(n2) 的, 至多更改 n 次可行顶标, 更改的复杂度是 O(n) 的, 所以找一条增广路的过程中, 改可行顶标的时间复杂度也是 O(n2) 的. 因为要执行n 次找增广路的过程, 所以总的时间复杂 度就是 O(n3) 的. Code: const maxn = 500; maxk = 10000; type integer = longint; var n, k, yy : integer; w : array [1..maxn, 1..maxn] of integer; slack, who, lx, ly : array [1..maxn] of integer; (*who[y]记录 x 对应的匹配点 y, x = min{l(x) +l(y ) −w(x , y ) = slack(y ) | x ∈S}*) (*lx 记录点集 X 的顶标, ly 记录点集 Y 的可行顶标*) link : array [1..maxn + 1] of integer; //记录点集 Y的匹配边 x, =0 说明没有 vx : array [1..maxn] of boolean; //x 是否在匈牙利树中 fa : array [1..maxn] of integer; //把y 加进匈牙利树的 x 的对应的匹配点 fin, fout : text; procedure readdata; var i, a, b : integer; begin readln(fin, n, k); for i := 1 to k do begin read(fin, a, b); readln(fin, w[a, b]);