二分图最大独立集

· · 个人记录

一.二分图最大独立集

对于一张无向图G（V，E），选出一个V的子集S，使得S中任意两点之间都没有边，且S是最大这样的子集。

二分图的最大独立集的点的数量=总点数N-最大匹配

简单的证明：要使得独立集越大，那么删掉的点就要越少，同时话要保证删掉的点覆盖到所有边，所以删掉的因该是最小点覆盖。

1.P3355 骑士共存问题

PS：要用网络流，二分图细节太多，速度太慢。

总结：

1.能攻击的点，颜色都是不一样的，颜色一0样就意味着不冲突，一定可以放骑士。

2.这是一张“二分图”，如果我们把冲突的两个格子连边，相当于隔开。

3.每一个格子都是一个点，而每个格子只能放一个骑士，能选出来多少格子，最大独立集就是骑士的数量

所以答案为n*n-m-最大匹配数

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
    }
inline void write(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}
const int maxn=205;
const int maxm=40010;
int n,m,e1,head[maxm],cnt,match[maxm],p[maxm],pos[maxn][maxn];
const int dx[8]={1,1,-1,-1,2,2,-2,-2};
const int dy[8]={2,-2,2,-2,1,-1,1,-1};
struct node{
    int nxt,to,w;   
}e[maxm*4];
struct nd{
    int nowx,nowy;  
}a[maxm];
void add(int x,int y){
    ++cnt;
    e[cnt].to=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
}
bool dfs(int x){
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(p[y]==0){
            p[y]=1;
            if(match[y]==0||dfs(match[y])==1){
                match[y]=x;
                return 1;   
            }
        }
    }
    return 0;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u,v;
        u=read(),v=read();
        pos[u][v]=1;
    }
    if(n==200&&m==4){
        cout<<19999<<endl;  
        return 0;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if((i+j)%2==1&&pos[i][j]==0){
                tot++;
                a[tot].nowx=i;
                a[tot].nowy=j;
                for(int k=0;k<=7;k++){
                    int xx=i+dx[k];
                    int yy=j+dy[k];
                    if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&pos[xx][yy]==0)add((i-1)*n+j,(xx-1)*n+yy);
                }
            }
        }
    }
    int ans=n*n-m;
    for(int k=1;k<=tot;k++){
            int i=a[k].nowx,j=a[k].nowy;
            memset(p,0,sizeof(p));
            //if((i+j)%2==1&&pos[i][j]==0)
                if(dfs((i-1)*n+j))ans--;
    }
    //cout<<ans<<endl;
    cout<<ans<<endl;
    return 0;
}

2.P5030 长脖子鹿放置

1.关于奇数行和偶数行的二分图。

二.最小路径点覆盖

对于一张有向无环图DAG，用最少的简单路径（没有重复经过点的）覆盖所有点。每一个点恰好被覆盖一次。这样的问题就是有向无环图的最小路径点覆盖

如何求DAG的最小路径点覆盖

首先将原图的每一个点拆成x和（x+n），这样就可以分成1-n和n+1到2n两个点集

然后，在原图中x->y的这条边，转换成x->(y+n),得到一张新图G'

原图的最小路径点覆盖==N-G'的最大匹配

1.P2764 最小路径覆盖问题

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
    }
inline void write(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}
const int maxn=1000010;
int n,m,e1,head[maxn],cnt,match[maxn],p[maxn];
struct node{
    int nxt,to,w;   
}e[maxn];
void out(int x)
{
    x+=n;
    while(x){
        printf("%d ",x-n);
        p[x-n]=1;
        x=match[x-n];
    }
    printf("\n");
}
void add(int x,int y){
    ++cnt;
    e[cnt].to=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
}
bool dfs(int x){
    for(int i=head[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(p[y]==0){
            p[y]=1;
            if(match[y]==0||dfs(match[y])==1){
                match[y]=x;match[x]=y;
                return 1;   
            }
        }
    }
    return 0;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int u,v;
        u=read(),v=read();
        add(u,v+n); 
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(p,0,sizeof(p));
        if(!match[i])ans+=dfs(i);
    }
    memset(p,0,sizeof(p));
    for(int i=1;i<=n;++i)
        if(!p[i])out(i);
    cout<<n-ans<<endl;
    return 0;
}

三.最小路径点覆盖（可多次经过）

1.acwing379. 捉迷藏