二分图

二分匹配

概念

  • 二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集 U 和V ，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。

例题

有n个人，其中有m对关系(x,y)表示x和y互相仇恨，x和y不能出现在同一个场合。问，能不能将这n个人，分成两组且每组之间任意两个人都不仇恨？

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
bool dfs(int now,int col)
{
    color[now] = col;
    for(int i = head[now];~i;i = edge[i].next){
        int to = edge[i].to;
        if(color[now] == color[to])return false;
        if(!color[to]){
            if(!dfs(to,3-col))return false;
        }
    }
    return true;
}

匹配

  • 匹配：在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。。

  • 匹配点、非匹配点、匹配边、非匹配边

  • 最大匹配：一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配。

有n个人，若干男生，若干女生，其中男女之间有m对关系(x,y)，表示x、y之间有好感，问你最多能挑多少对人，使得每一对都是有好感的（每个人只能被挑一次）

how?

匈牙利算法：O(VE)

概念

  • 交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边…形成的路径叫交替路。

  • 增广路：从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。

增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
bool findp(int now)
{
    for(int i = head[now];~i;i = edge[i].next)
    {
        int to = edge[i].v;
        if(!vis[to])
        {
            vis[to] = true;
            if(matching[to] == -1 || findp(matching[to]))
            {
                matching[now] = to;
                matching[to] = now;
                return true;
            }
        }
    }
    return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
int hung(int n)
{
   int ans = 0;
   for(int i = 1;i <= n ;i++)
   {
       if(matching[i] == -1){
            memset(vis,0,sizeof(vis));
            if(findp(i))ans++;
       }
   }
   return ans;
}

进阶

接下来这部分会稍微有些难咯

一些概念

前方信息量爆炸

  • 最小边覆盖：最少的边覆盖所有点
  • 最小点覆盖：最少的点覆盖所有边
  • ==二分图==的最大匹配 = 最小点覆盖
  • ==二分图==的最小边覆盖=顶点数-最大匹配

微信截图_20200318023053

  • 最大团&最大独立集：最大的点集，任意两点之间都有边/都没边
  • 对于不存在孤点的任意图，最大匹配+最小边覆盖=顶点数
  • ==任意图==中，最大独立集+最小点覆盖=顶点数
  • DAG中不可相交的最小路径/链覆盖
  • DAG中可相交的最小路径/链覆盖
  • DAG中最长反链=可相交的最小路径覆盖（DAG中闭包传递后的最大独立集）

END?

图论的精髓 ： 建图

给你一个国际象棋的棋盘，让你放尽可能多的马，使得这些马互相无法攻击到？

因为疫情，大家都不想在电影院离得太近，每个人x曼哈顿距离内都不想有其他人，问怎么安排使得做的人做多？

微信图片_20200318030348

给你个棋盘，棋盘上某些位置有棋子，每行每列最多只能选一个棋子，让你选尽可能多的棋子

给一个数k，问他的正整数倍数中，（十进制下）每一位的和最小是多少,2\leq k \leq 10^{5}

  • 从1开始 ， 建立一个数x到x+1和x*10分别为1和0的边，最后找到最快到达的k的倍数，即答案最短路

有一条线段，1到n，n个位置，你有m个棋子，现在你可以在每个位置放一些棋子，给你q个区间条件a,b,c，表示[a,b]区间最少要有c个棋子，问你至少要用多少个棋子

  • d_{i}表示前i个位置的棋子个数，对于条件，则是d_{b}-d_{a-1} \ge c
  • d_{i+1} - d_{i} \ge 0
  • d_{n} - d_{0} \le m
  • 二分+差分约束spfa判断是否有解