拟阵交

给定两个拟阵(M_1(S,I_1),M_2(S,I_2))求两个拟阵的一个独立集(I)使得(Iin I_1,Iin I_2)(I)满足一定条件(比如(|I|)最大,(|I|)最大的同时(I)中元素权值和最大之类)

我们采用增量法

定义交换图(D_{M1,M2})

(yin I,xin Sackslash I)(I-y+xin I_1)时,我们从(y)(x)连一条边

(yin I,xin Sackslash I)(I-y+xin I_2)时,我们从(x)(y)连一条边

我们找到集合(X_1={ x|I+x in I_1,xin Sackslash I },X_2={x|I+x in I_2,xin Sackslash I})

我们每次找到一条(X_1)(X_2)的最短路径(经过点数最少)即可

然后我们把路径上不在(I)中的点加入,在(I)中的点剔除

然后重建交换图

如果要求(|I|)最大的同时(I)中元素权值和最大,那么我们找经过点数最少的同时权值和最大的路径即可

原文地址:https://www.cnblogs.com/invisible-eyes/p/12872042.html