二分图（粗糙的体会）

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

相关定义

二分图（偶图）是一种无向图：其中的顶点可以分为两个交集为空的集合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;
}

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

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