二分图及其衍生

目录

1.关押罪犯(二分+染色法)

2.棋盘覆盖（最大匹配数）

3.机器任务（最小点覆盖）

4.骑士放置（最大独立集）

5.捉迷藏（最小路径重复点覆盖）

---

1.关押罪犯(二分+染色法)

257. 关押罪犯 - AcWing题库

二分罪犯的冲突事件的影响力，二分的条件是大于mid的罪犯的怒气值放在不同的监狱，然后用染色法，假如没冲突就，缩小mid

#include
using namespace std;
const int N=20010,M=200010;
int n,m;
int h[N],e[M],ne[M],idx,w[M];
int color[N];//0表示还没颜色，1表示染黑色，2表示白色
void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u,int c,int mid)//染到u这个点，目前颜色为c,二分值为mid
{
    color[u]=c;//让这个点颜色为c
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(w[i]<=mid) continue;//假如小于就不用处理了
        if(color[j])//假如有颜色了
        {
            if(color[j]==c) return false; //假如颜色相同的话，则不符合
        }
        else if(!dfs(j,3-c,mid)) return false;//3-c就是给j这个点然另一种颜色
    }
    return true;
}
bool check(int mid)
{
    memset(color,0,sizeof color);//清空
    for(int i=1;i<=n;i++)
        if(!color[i])//假如没有被染色过
          if(!dfs(i,1,mid)) return false;//假如染色后不成立
    return true;
}
int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    int l=0,r=1e9;
    while(l//二分查找最小冲突事件的影响力
    {
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<
    return 0;
}

增广路径：从非匹配点走然后非匹配边然后匹配边然后非匹配然后匹配....最后是非匹配点

最大匹配等价于不存在增广路径

2.棋盘覆盖（最大匹配数）

372. 棋盘覆盖 - AcWing题库

#include
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N=110;
pii match[N][N];
bool st[N][N],g[N][N];
int n,m,res=0;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
bool find(int x,int y)//帮x,y这个点找对象
{
    for(int i=0;i<4;i++)//枚举他可能的对象
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<1||a>n||b<1||b>n) continue;//假如越界
        if(st[a][b]||g[a][b]) continue;//假如这个点有其他的对象
        st[a][b]=true;//先标记这个点有对象了
        pii t=match[a][b];
        if(t.x==0||find(t.x,t.y))//假如这个点还没对象或者这个点有对象，但是可以让给别人
        {
            match[a][b]={x,y};//则把a,b给x,y
            return true;
        }
    }
    return false;//反之没对象
}
int  main()
{
   cin>>n>>m;
   while(m--)
   {
       int a,b;
       cin>>a>>b;
       g[a][b]=true;
   }
   for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
       if((i+j)&1&&!g[i][j])//枚举奇数的情况
        { 
            memset(st,0,sizeof st); //清空上一层的状态
           if(find(i,j)) res++;//假如这个点找的到对象，则答案++
        }
   cout<
    return 0;
}

最小点覆盖：每条边至少选出一个点，使得选出的点最小就是最小点覆盖

最小点覆盖 等于 最大匹配数 

3.机器任务（最小点覆盖）

376. 机器任务 - AcWing题库

这题ai与bi可以看成ai->bi，然后答案就是选最少的点使得所有边都覆盖了，其实就是最小点覆盖问题，就是求最大匹配数即可

#include
using namespace std;
const int N=110;
bool g[N][N],st[N];
int match[N];
int n,m,k;
bool find(int u)//帮u找女朋友
{
    for(int i=1;i//枚举可能的女朋友
     if(!st[i]&&g[u][i])//假如这个女朋友没有男朋友并且我跟他有关系
     {
         st[i]=true;//标记这个点有男朋友了
         int t=match[i];//找一下这个点的男朋友
         if(t==0||find(t))//假如没男朋友或者她男朋友可以换个女朋友
         {
             match[i]=u;//则让她的男朋友是我
             return true;//返回找到了
         }
     }
     return false;//反之没女朋友
}
int  main()
{
    while(cin>>n,n)
    {
        memset(g,0,sizeof g);//清空
        memset(match,0,sizeof match);//清空
        cin>>m>>k;
        while(k--)
        {
            int t,a,b;
            cin>>t>>a>>b;
            g[a][b]=true;//从a->b连条边
        }
        int res=0;
        for(int i=1;i
        {
            memset(st,0,sizeof st);//清空
            if(find(i)) res++;//假如匹配成功
        }
        cout<
    }
    return 0;
}

最大独立集：一个图中，选出最多的点，使得选出的点内部没有边 

最大团：一个图中，选出最多的点，使得选出的点任意两点都有边

最大独立集与最大团互补

最大独立集等价于在原图中破环最少的点，将所有边都破坏掉

等价于 找最小点覆盖 等价于 找最大匹配

4.骑士放置（最大独立集）

378. 骑士放置 - AcWing题库

把所有可以攻击到的马连条边，则答案就是求两两不能攻击到的马，也即最大独立集的问题

把奇数和偶数分别为两个集合，也即符合二分图，然后八个方向攻击到的格子都与自己的格子的奇偶性不同，所有可以用二分图最大独立集来求解

答案就是n*m-k-最大匹配数

#include
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;
const int N=110;
bool g[N][N],st[N][N];
pii match[N][N];
int n,m,k;
int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={1,2,2,1,-1,-2,-2,-1};//八个方向
bool find(int x,int y)
{
   for(int i=0;i<8;i++)//枚举可能的女朋友
   {
       int a=x+dx[i],b=y+dy[i];
       if(a<1||a>n||b<1||b>m) continue;//假如越界
       if(st[a][b]||g[a][b]) continue;//假如已经有男朋友了，或者是坏格子
       st[a][b]=true;//标记这个点已经有男朋友了
       pii t=match[a][b];
       if(t.x==0||find(t.x,t.y))//假如没有男朋友或者这个男的可以换个女朋友
       {
           match[a][b]={x,y};//就把这个女的抢过来给我
           return true;//返回有女朋友
       }
   }
     return false;//反之没
}
int  main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)//标记所有坏的格子
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=true;
    }
    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
          if(!g[i][j]&&(i+j)&1)//假如是奇数和不是坏格子
           {
              memset(st,0,sizeof st);//清空
              if(find(i,j)) res++;//假如找的到女朋友
           }
    cout<//输出最大独立集
    return 0;
}

最小路径点覆盖： 对于一个有向无环图（DAG），用最少的互不相交的路径将所有点覆盖

最小路径重复点覆盖：求一遍原图的传递闭包，再求一遍最小路径点覆盖则就是

5.捉迷藏（最小路径重复点覆盖）

379. 捉迷藏 - AcWing题库

题目就是从任意一个点出发，都不能走到另外一个点，答案就是n-最小路径重复点覆盖

#include
using namespace std;
const int N=210;
bool g[N][N],st[N];
int match[N];
int n,m;
bool find(int x)//帮x找女朋友
{
    for(int i=1;i<=n;i++)//枚举可能的女朋友
        if(!st[i]&&g[x][i])//假如这个女的没男朋友并且我跟他有关系
        {
           st[i]=true;//标记这个女的找到了男朋友
           int t=match[i];
           if(t==0||find(t))//假如这个女的没男朋友或着那男的可以换个女朋友
           {
               match[i]=x;//则把这个女的让给我
               return true;//返回找到了
           }
        }
    return false;//反之找不到
}
int  main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]=true;
    }
    //做一遍传递闭包
    for(int k=1;k<=n;k++)//floryd求传递闭包
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
             g[i][j]|=g[i][k]&g[k][j];
    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);//清空
        if(find(i)) res++;//假如找的到女朋友
    }
    cout<//输出最大路径重复点覆盖
    return 0;
}