二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
1.二分图的判定：不存在奇数环或染色法不生产矛盾。
关押罪犯
二分 + 二分图。
对于一个二分点mid，如果仇恨值大于mid的所有罪犯在二分图的两个集合内，mid就是合法的。所以只需要判断大于mid的关系是否构成二分图。
代码：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 6 using namespace std; 7 8 const int N = 20010, M = 200010; 9 10 int n, m; 11 int h[N], e[M], w[M], ne[M], idx; 12 int color[N]; 13 14 void add(int a, int b, int c) 15 { 16 e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++; 17 } 18 19 20 bool dfs(int u, int c, int mid) 21 { 22 color[u] = c; 23 for(int i = h[u] ; ~i ; i = ne[i]) 24 { 25 int j = e[i]; 26 if(w[i] <= mid)continue;//小于mid的边就不用管 27 if(color[j]) 28 { 29 if(color[j] == c)return false; 30 } 31 else if(!dfs(j, 3 - c, mid))return false; 32 } 33 return true; 34 } 35 36 bool check(int mid) 37 { 38 memset(color, 0, sizeof color); 39 for (int i = 1; i <= n; i ++ ) 40 if (!color[i])//未染色就染色 41 if (!dfs(i, 1, mid)) 42 return false; 43 return true; 44 } 45 46 int main() 47 { 48 scanf("%d%d", &n, &m); 49 memset(h, -1, sizeof h); 50 51 while (m -- ) 52 { 53 int a, b, c; 54 scanf("%d%d%d", &a, &b, &c); 55 add(a, b, c), add(b, a, c); 56 } 57 58 int l = 0, r = 1e9; 59 while (l < r) 60 { 61 int mid = l + r >> 1; 62 if (check(mid)) r = mid; 63 else l = mid + 1; 64 } 65 66 printf("%d\n", r); 67 68 return 0; 69 }
二分图的最大匹配
棋盘覆盖
可以将棋盘的每一个格子看做一个点，相邻的格子看做一条边，将格子的横纵坐标相加的值为奇数或偶数分为两边，可以得知是一个二分图，题意就变成求二分图的最大匹配问题。
代码：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 6 #define x first 7 #define y second 8 9 using namespace std; 10 11 typedef pair<int, int> PII; 12 13 const int N = 110; 14 15 bool g[N][N], st[N][N]; 16 PII match[N][N]; 17 int n, m; 18 int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; 19 20 21 bool find(int x, int y) 22 { 23 for(int i = 0 ; i < 4 ; i ++) 24 { 25 int a = x + dx[i], b = y + dy[i]; 26 if(a < 1 || b < 1 || a > n || b > n)continue; 27 if(st[a][b] || g[a][b])continue; 28 st[a][b] = true; 29 PII t = match[a][b]; 30 if(t.x == -1 || find(t.x, t.y)) 31 { 32 match[a][b] = {x, y}; 33 return true; 34 } 35 } 36 return false; 37 } 38 39 int main(){ 40 scanf("%d%d", &n, &m); 41 42 while(m --) 43 { 44 int x, y; 45 scanf("%d%d", &x, &y); 46 g[x][y] = true; 47 } 48 49 memset(match, -1, sizeof match); 50 51 int res = 0; 52 for(int i = 1 ; i <= n ; i ++) 53 for(int j = 1 ; j <= n ; j ++) 54 if((j + i) % 2 && !g[i][j])//奇数点偶数点对称，选一种就可以 55 { 56 memset(st, 0, sizeof st); 57 if(find(i, j))res ++;//能找到匹配就加上 58 } 59 60 printf("%d\n", res); 61 return 0; 62 }
最小点覆盖：每一条边至少有一个点被选出
在二分图中，最小点覆盖 = 最大匹配数。
机器任务
可以将题目中的a[i]向b[i]连一条边，转换成，a[i]到b[i]的边上至少要有一个被选点，求最小点覆盖。
代码：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 6 using namespace std; 7 8 const int N = 110; 9 int match[N]; 10 bool st[N], g[N][N]; 11 int n, m, k; 12 13 bool find(int x) 14 { 15 for(int i = 1 ; i < m ; i ++) 16 if(!st[i] && g[x][i]) 17 { 18 st[i] = true; 19 if(match[i] == -1 || find(match[i])) 20 { 21 match[i] = x; 22 return true; 23 } 24 } 25 return false; 26 } 27 28 int main(){ 29 while(cin >> n, n) 30 { 31 cin >> m >> k; 32 memset(match, -1, sizeof match); 33 memset(g, 0, sizeof g); 34 35 while(k --) 36 { 37 int t, a, b; 38 cin >> t >> a >> b; 39 if(!a || !b)continue;//刚开始是0就直接完成，无需记录 40 g[a][b] = true; 41 } 42 43 int res = 0; 44 for(int i = 1 ; i < n ; i ++) 45 { 46 memset(st, 0, sizeof st); 47 if(find(i))res ++; 48 } 49 50 51 cout << res << endl; 52 } 53 54 55 return 0; 56 }
最大独立集：从图中选最多的点，使得选出的点之间（作为一个集合内部）无边。
最大团：从图中选最多的点，使得选出的点之间（作为一个集合内部）有边。
在二分图中 求最大独立集<->先求去掉最少的点，将所有边破坏<->先求最小点覆盖<->先求最大匹配。
所以最大独立集 = 总数 - 最大匹配。
骑士放置
这题也可以用状压DP做。
将每个格子看做一个点，关系看做一条边，题意就变成选取最多的点，使每个点之间无边，格子的总数减去最大匹配和不能填的点数，即为答案。
代码：
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 6 #define x first 7 #define y second 8 9 using namespace std; 10 11 typedef pair<int,int> PII; 12 13 const int N = 110; 14 15 PII match[N][N]; 16 bool st[N][N], g[N][N]; 17 int n, m, k; 18 19 int dx[8] = {-1, 1, 2, 2, 1, -1, -2, -2}; 20 int dy[8] = {2, 2, 1, -1, -2, -2, -1, 1}; 21 22 bool find(int x, int y) 23 { 24 for(int i = 0 ; i < 8 ; i ++) 25 { 26 int a = x + dx[i], b = y + dy[i]; 27 if(a < 1 || b < 1 || a > n || b > m)continue; 28 if(g[a][b] || st[a][b])continue; 29 st[a][b] = true; 30 PII t = match[a][b]; 31 if(t.x == 0 || find(t.x, t.y)) 32 { 33 match[a][b] = {x, y}; 34 return true; 35 } 36 } 37 return false; 38 } 39 40 int main(){ 41 cin >> n >> m >> k; 42 43 for(int i = 0 ; i < k ; i ++)//下面需要用到k，不能用while(k --) 44 { 45 int x, y; 46 cin >> x >> y; 47 g[x][y] = true; 48 } 49 50 int res = 0; 51 for(int i = 1 ; i <= n ; i ++) 52 for(int j = 1 ; j <= m ; j ++) 53 if((i + j) % 2 && !g[i][j]) 54 { 55 memset(st, 0, sizeof st); 56 if(find(i, j))res ++; 57 } 58 59 cout << n * m - k - res << endl; 60 return 0; 61 }