二分图(粗糙的体会)

2022/8/11 6:26:52

本文主要是介绍二分图(粗糙的体会),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

相关定义

二分图(偶图)是一种无向图:其中的顶点可以分为两个交集为空的集合X和Y,对于途中的每条边,其中一个端点在X中,另一个端点在Y中,且X和Y内部顶点之间没有边。

完全二分图:集合X和Y每对顶点之间有且仅有一条边的图,记作\(K_{n,m}\),n和m分别为X和Y集合中的顶点个数。

匹配:任意两条边都没有相同的顶点,则称这些边为一组匹配。

最大匹配:图中包含边数最多的匹配称为图的最大匹配。。

完备匹配:如果所有点都在匹配边上,则称这个最大匹配是完美匹配。

交错路径:如果P是G中一条路径,并且对于P上每一对相邻的边(端点包含同一个顶点),都满足其中一条在匹配M中,而另一条不存在。

增广路径:P是一条交错路径,并且起点和终点都未被匹配。

判断方式

点染色法

DFS跑一遍图,交替染色,如果能成功完成对全图的染色,则该图是二分图。

代码实现

inline bool check()
{
  memset(c, 0, sizeof(c));
  rep(i,1,n)
  {
    if (!c[i])
    {
      c[i] = 1;
      if (!dfs(i)) return false;
    }
  }
  return true;
}


inline void dfs(int u)
{
  for (auto v : e[u])
    if (!c[v]) 
    {
      c[v] = 3 - c[u];
        if (dfs(v)) return false;
    }
    else
    {
      if (c[v] == c[u]) return false;
    }
  return true;
}

二分图最大匹配

现有方案为M,如果能找到一条增广路P,那么M ^ P就是一组更有的匹配。

代码实现

\(O(nm)\)

bool find(int x)
{
  st[x] = true;
  for (auto y : e[x])
  {
    if (!v[y] || (!b[v[y]] && find(v[y])))
    {
      v[y] = x;
      return true;
    }
  }
  return false;
}

int match()
{
  int ans = 0;
  memset(v, 0, sizeof(v));
  for (int i = 1; i <= n1; i++)
  {
    memset(b, false, sizeof(b));
    if (find(i))
      ++ans;
  }
  return ans;
}

例题

棋盘覆盖问题

题面

现在有一个\(n\)行\(n\)列的棋盘,坐标范围从 \((1,1)−(n,n)\),你需要用 \(1 \times 2\)的多米诺骨牌去覆盖这张棋盘。

这张棋盘上有\(m\)个格子已经放置了棋子,即这些格子不能被覆盖,现在要你求出骨牌最多可以覆盖多少个格子。

第一行输入\(n,m\)。

接下来\(m\)行,每行两个数字\(x_i,y_i\)表示棋子的坐标。

输出一个数表示最多覆盖的格子数。

思路

把棋盘黑白染色后可以建出一个二分图,骨牌的形状相当于一个黑格+一个白格,也就是二分图中的一组匹配。那么问题就转变成了在这个二分图上得到最大匹配数。

代码实现

时间复杂度\(O(n^4)\)

vector<int> e[N * N];
int n, m, a[N][N], n1, n2, r[N][N], v[801];
bool b[801];
int D[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

// r:第i行第j列格子是左边第几个点或者右边第几个点
// v:右边连的哪个点 b:是否被搜过
// n1 n2 左右两边点集合

bool find(int x) 
{
  b[x] = true;
  for (auto y : e[x])
    if (!v[y] || (!b[v[y]] && find(v[y])))
    {
      v[y] = x;
      return true;
    }
  return false;
}

int match() 
{
  int ans = 0;
  memset(v, 0, sizeof(v));
  rep(i,1,n1)
  {
    memset(b, false, sizeof(b));
    if (find(i)) ++ans;
  }
  return ans;
}

int main(void)
{
  n = read(), m = read();
  memset(a, 0, sizeof(a));
  n1 = n2 = 0;
  rep(i,1,m)
  {
    int x, y;
    x = read(), y = read();
    a[x][y] = 1;
  }
  
  rep(i,1,n) rep(j,1,n)
    if (!a[i][j])
      if ((i + j) & 1) r[i][j] = ++n2;
      else r[i][j] = ++n1;

  rep(i,1,n) rep(j,1,n)
  {
    if (!a[i][j] && !((i + j) & 1)) 
      rep(k,0,3) 
      {
        int x = i + D[k][0], y = j + D[k][1];
        if (x < 1 || x > n || y < 1 || y > n || a[x][y]) continue;
        e[r[i][j]].push_back(r[x][y]);
      }
  }

  printf("%d\n",match() * 2);

  return 0;
}

最大独立集

在图中选出最多的点,满足两两之间没有边相连,答案就是点数减去最大匹配里的点。

代码实现

inline bool find(int x) 
{
  b[x] = true;
  for (auto y : e[x])
    if (!v[y] || (!b[v[y]] && find(v[y])))
    {
      v[y] = x;
      return true;
    }
  return false;
}

inline int match() 
{
  int ans = 0;
  memset(v, 0, sizeof(v));
  rep(i,1,n1)
  {
    memset(b, false, sizeof(b));
    if (find(i)) ++ans;
  }
  return ans;
}

inline void dfs(int u)
{
  for (auto v : e[u])
    if (!c[v]) c[v] = 3 - c[u], dfs(v);
}

例题

题面

给你一张二分图,图中没有重边,你需要求出这张图中最大独立集包含的顶点个数。

最大独立集是指:在图中选出最多的点,满足他们两两之间没有边相连。

图用以下形式给出:

第一行输入两个整数 \(n,m\),表示图的顶点数和边数,顶点编号从 \(1\) 到$ n$。

接下来 \(m\) 行,每行两个整数 \(x,y\),表示 \(x\) 和 \(y\) 之间有一条边。

输出一个数为最大独立集大小。

思路

先把图存下来,通过染色法把图的左右两边标记出来,重新建图得到我们想要的二分图。接下来套最大匹配的板子。

代码实现

const int N = 10001;

vector<int> e[N];
int n, m, c[N], a[N][2], n1, n2, v[N], r[N];
bool b[N];

inline int read()
{
  int f = 1, x = 0;char ch = getchar();
  while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
  while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
  return x * f;
}

inline bool find(int x) 
{
  b[x] = true;
  for (auto y : e[x])
    if (!v[y] || (!b[v[y]] && find(v[y])))
    {
      v[y] = x;
      return true;
    }
  return false;
}

inline int match() 
{
  int ans = 0;
  memset(v, 0, sizeof(v));
  rep(i,1,n1)
  {
    memset(b, false, sizeof(b));
    if (find(i)) ++ans;
  }
  return ans;
}

inline void dfs(int u)
{
  for (auto v : e[u])
    if (!c[v]) c[v] = 3 - c[u], dfs(v);
}

int main(void)
{
  n = read(), m = read();

  rep(i,1,m)
  {
    a[i][0] = read(), a[i][1] = read();
    e[a[i][0]].push_back(a[i][1]);
    e[a[i][1]].push_back(a[i][0]);
  }

  memset(c, 0, sizeof(c));
  rep(i,1,n) 
    if (!c[i]) c[i] = 1, dfs(i);

  n1 = 0, n2 = 0;
  rep(i,1,n)
    if (c[i] == 1) r[i] = ++n1;
    else r[i] = ++n2;
  
  rep(i,1,n) e[i].clear();

  rep(i,1,m)
  {
    int x = a[i][0], y = a[i][1];
    if (c[x] == 1) e[r[x]].push_back(r[y]);
    else e[r[y]].push_back(r[x]);
  }

  printf("%d\n",n - match());
  return 0;
}

最小路径覆盖

题面

给你一张有向无环图,你需要求出最少用多少条互不相交的路径可以覆盖图中所有顶点。

两条路径不相交是指两条路径不经过同一个点。

路径可以不包含边。

图用以下形式给出:

第一行输入两个整数 \(n,m\),表示图的顶点数和边数,顶点编号从 \(1\) 到 \(n\)。

接下来 \(m\) 行,每行两个整数 \(x,y\),表示 \(x\) 和 \(y\) 之间有一条边。

输出一个数为最少的路径条数。

思路

把一个点拆成两个点,左边是出度,右边都是入度,这样一来可以得到一个二分图,再求一下最大匹配数目,答案就是总点数减去最大匹配数。

因为一开始每个点都是独立的,每连通一条边,答案就减少一。

代码实现

const int N = 1010;

vector<int> e[N];
int n, m, v[N];
bool b[N];

inline int read()
{
  int f = 1, x = 0;char ch = getchar();
  while (ch > '9' || ch < '0'){if (ch == '-')f = -f;ch = getchar();}
  while (ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
  return x * f;
}

inline bool find(int x) 
{
  b[x] = true;
  for (auto y : e[x])
    if (!v[y] || (!b[v[y]] && find(v[y])))
    {
      v[y] = x;
      return true;
    }
  return false;
}

inline int match() 
{
  int ans = 0;
  memset(v, 0, sizeof(v));
  rep(i,1,n)
  {
    memset(b, false, sizeof(b));
    if (find(i)) ++ans;
  }
  return ans;
}

int main(void)
{
  n = read(), m = read();
  rep(i,1,m)
  {
    int x, y;
    x = read(), y = read();
    e[x].emplace_back(y);
  }
  printf("%d\n",n - match());
  return 0;
}

感觉体会不是很深刻,刷套相关题目加深理解后再补几篇题解吧(挖个坑)



这篇关于二分图(粗糙的体会)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程