最大独立集证明参考:https://blog.csdn.net/qq_34564984/article/details/52778763

最大独立集证明:

Girls and Boys HDU - 1068  二分图匹配(匈牙利)+最大独立集证明-LMLPHP

上图,我们用两个红色的点覆盖了所有边。我们证明的前提条件是已经达到最小覆盖。

即条件1.已经覆盖所有边,条件2.所用的点数最小

首先我们来证明蓝色点组成的是一个独立集:如果有两个蓝色点间有边相连,那么这条

边则没有被覆盖,则与条件1矛盾。因此是独立集。

再来证明这个独立集最大: 如果我们要再增加这个独立集中的点,则需要把某个红点变

成蓝点。而由最小覆盖数=最大匹配数的证明我们知道,每一个红点是最大匹配中的一

个匹配点,也就是说每个红点至少连接了一条边。因此当我们将某个红点变成蓝点

时,我们需要牺牲的蓝点的个数是大于等于1的。也就是说,我们最多只能找到数量相等

的其他独立集,而无法找到数量更大的。因此蓝色点集必定为最大独立集。 蓝色点数 =

总点数 - 红色点数,即最大独立集=总数-最小覆盖集。

 #include<bits/stdc++.h>
using namespace std;
const int maxn=+;
int mp[maxn][maxn],girl[maxn],used[maxn];
void init(){
memset(mp,,sizeof(mp));
memset(girl,,sizeof(girl));
}
int n;
bool find(int x){
for(int i=;i<=n;i++){
if(mp[x][i]&&used[i]==){
used[i]=;
if(girl[i]==||find(girl[i])){
girl[i]=x;
return ;
}
}
}
return ;
}
int main(){
while(scanf("%d",&n)==){
int temp;
int a;
char c;
init();
for(int i=;i<=n;i++){
scanf("%d%c%c%c%d%c",&temp,&c,&c,&c,&temp,&c);
//getchar();
for(int j=;j<=temp;j++){
scanf("%d",&a);
mp[i][a+]=;
}
}
int sum=;
/*for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cout<<mp[i][j]<<" ";
}
cout<<endl;
}*/
for(int i=;i<=n;i++){
memset(used,,sizeof(used));
if(find(i))sum++;
}
printf("%d\n",n-sum/);
}
return ;
}
05-11 09:39