祎隋

关于二分图的最小顶点覆盖和最大独立集
二分图的最小顶点覆盖定义选定一个点则与其连边将被覆盖,然后我们求最小顶点覆盖完整个二分图结论:最小顶点覆盖等于二分...
扫描右侧二维码阅读全文
03
2019/04

关于二分图的最小顶点覆盖和最大独立集

二分图的最小顶点覆盖

定义选定一个点则与其连边将被覆盖,然后我们求最小顶点覆盖完整个二分图

结论:最小顶点覆盖等于二分图最大匹配

(最小割等于最大流)

二分图的最大独立集

选出顶点使顶点间两两不相邻,选出顶点的集合称为独立集,求最大独立集

结论:最大独立集=总点数-最小顶点覆盖(最大匹配)

例题:叶片(多校联考省选模拟)

Description

一个圆形涡轮上有N 个叶片均匀围成一圈,按顺时针1 到N 标号,其中有一些叶片损坏了。现在要把损坏的叶片给拆下来,但是为了使涡轮正常工作,它的重心还应该落在中心上。求最少还要再拆下几个叶片才能实现目标。

Solve

考虑到n最多两个质数,那么贪心,对一个质数p,设x=n/p,那么可以得到序列:
1,x+1,2*x+1....
2,x+2,2*x+2....
....
x-1,2*x-1,......
那么对于另外一个质数也是一样的,所以我们将有交集的两两连边,然后求一个最大独立集即可。

Code:

#include<bits/stdc++.h>
using namespace std;
const int nn=60005;
int N,M,Bel[nn],Ans,S,T;
int Tot=1,F[nn],To[nn],Nxt[nn],W[nn];
void Adde(int u,int v,int w){
    To[++Tot]=v; Nxt[Tot]=F[u]; W[Tot]=w; F[u]=Tot;
    To[++Tot]=u; Nxt[Tot]=F[v]; W[Tot]=0; F[v]=Tot;
}
int Dep[nn]; 
bool Bfs(){
    for(int i=1;i<=T;i++) Dep[i]=0;
    Dep[T]=1; queue<int>q; q.push(T);
    while(!q.empty()){
        int t=q.front(); q.pop();
        for(int i=F[t];i;i=Nxt[i]){
            int v=To[i]; if(!W[1^i]||Dep[v]) continue ;
            Dep[v]=Dep[t]+1; q.push(v);
        }
    } return Dep[S];
}
int Dfs(int u,int fl){
    int nw=fl;
    if(u==T) return fl;
    for(int i=F[u];i;i=Nxt[i]){
        int v=To[i]; if(!W[i]||Dep[v]+1!=Dep[u]) continue ;
        int d=Dfs(v,min(fl,W[i])); if(!d) continue ;
        W[i]-=d; W[i^1]+=d; fl-=d; if(!fl) return nw;
    } return nw-fl;
}
int main(){
    scanf("%d%d",&N,&M); int p1,p2,g1,g2;
    for(p1=2;p1<N;p1++)if(N%p1); else break ;
    for(p2=p1+1;p2*p2<=N;p2++)if(N%p2); else break ;// printf("%d %d\n",p1,p2);
    for(int x,i=1;i<=M;i++){ scanf("%d",&x); Bel[x]=-1; }    
    if(N%p2){
        g1=N/p1;
        for(int i=1;i<=g1;i++){
            int flg=1;
            for(int j=i;j<=N;j+=g1)if(Bel[j]){ flg=0; break ; }
            if(flg) Ans+=p1; 
        } printf("%d\n",Ans==0?-1:N-Ans-M);
    }
    else {
        S=(N<<1)+1; T=(N<<1)+2;
        g1=N/p1; g2=N/p2;
        for(int i=1;i<=g1;i++){
            int flg=1;
            for(int j=i;j<=N;j+=g1)if(Bel[j]==-1) flg=0; else Bel[j]=i;
            if(flg) Ans+=p1,Adde(S,i,p1);  
        }
        for(int i=1;i<=g2;i++){
            int flg=1;
            for(int j=i;j<=N;j+=g2)if(Bel[j]==-1){ flg=0; break ; } 
            if(flg){
                Ans+=p2; Adde(i+N,T,p2);
                for(int j=i;j<=N;j+=g2) Adde(Bel[j],i+N,0x3f3f3f3f);
            }
        } while(Bfs()) Ans-=Dfs(S,0x3f3f3f3f); printf("%d\n",Ans==0?-1:N-Ans-M);
    }
    return 0;
} 

二分图的最大团

最大团就是二分图中最大的完全图,其子图可以是一个完全图。
结论:二分图的最大团=补图的最大独立集
对于构造补图:对于两点u,v,若原图中存在一条边连接,则补图不连接,否则连接。

Last modification:April 3rd, 2019 at 10:51 am

Leave a Comment