本文共 6584 字，大约阅读时间需要 21 分钟。

输入

5 5 100 1 11 1 22 1 33 1 44 2 15 2 26 2 37 2 48 3 39 4 30

输出

3

在二分图中我们经常要找题目中的 “0要素” 和 “1要素” ，作为解答的突破口。

二分图最小覆盖模型的特点则是：每条边有2个端点，二者至少选择一个。我们不妨称之为 “2元素”。

如果题目具有 “2元素” 的特点，那么可以尝试抽象成二分图的最小覆盖模型求解。

AC代码

#include
   
    using namespace std;const int N = 110;int n, m, k, f[N], ans;bool v[N];vector
    
     e[N];bool dfs(int x) {	for (int i = 0; i < e[x].size(); ++i) {		int y = e[x][i];		if (v[y])continue;		v[y] = true;		if (!f[y] || dfs(f[y])) {			f[y] = x;			return 1;		}	}	return 0;}int main() {	//freopen("in.txt", "r", stdin);	while (cin >> n && n) {		cin >> m >> k;		for (int i = 0; i < n; ++i)e[i].clear();		for (int i = 0; i < k; ++i) {			int x, y;			cin >> i >> x >> y;			if (x && y)e[x].push_back(y);		}		memset(f, 0, sizeof f);		ans = 0;		for (int i = 1; i < n; ++i) {			memset(v, 0, sizeof v);			ans += dfs(i);		}		cout << ans << endl;	}}
    
   

题目描述

输入

4 4*.*..******...*.

输出

4

备注:

OUTPUT DETAILS:Boards 1, 2, 3 and 4 are placed as follows:1.2..333444...2.Board 2 overlaps boards 3 and 4.

题目大意：用木板将'*'覆盖，同一行或同一列的'*'可以用一块木板覆盖，'.'不能被覆盖。问最少用多少块木板可以把全部的'*'覆盖?

解题思路：二分匹配的经典构图题目

所以用匈牙利求最大匹配数即可

构图的代码要好好再看看！

#include
   
    using namespace std;const int N = 56;int n, m, tot = 1, a[N][N][2], f[N * N], ans;char s[N][N];bool v[N * N];vector
    
      e[N * N];bool dfs(int x) {	for (unsigned int i = 0; i < e[x].size(); i++) {		int y = e[x][i];		if (v[y]) continue;		v[y] = 1;		if (!f[y] || dfs(f[y])) {			f[y] = x;			return 1;		}	}	return 0;}int main() {	//freopen("in.txt", "r", stdin);	cin >> n >> m;	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);	for (int i = 1; i <= n; i++)		for (int j = 1; j <= m + 1; j++)//m + 1			if (s[i][j] == '*') a[i][j][0] = tot;			else ++tot;	int t = tot;	for (int j = 1; j <= m; j++)		for (int i = 1; i <= n + 1; i++)			if (s[i][j] == '*') a[i][j][1] = tot;			else ++tot;	for (int i = 1; i <= n; i++)		for (int j = 1; j <= m; j++)			if (s[i][j] == '*') {				e[a[i][j][0]].push_back(a[i][j][1]);				e[a[i][j][1]].push_back(a[i][j][0]);			}	for (int i = 1; i < t; i++) {		memset(v, 0, sizeof(v));		ans += dfs(i);	}	cout << ans << endl;}
    
   

(二分图的最大独立集)

题目描述

输入

2 3 0

输出

4

若两个格子是“日”字的对角（能相互攻击），则在它们对应的节点之间连边。

#include
   
    using namespace std;const int N = 105;int n, m, t, ans, fx[N][N], fy[N][N];bool a[N][N], v[N][N];const int dx[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };const int dy[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };bool dfs(int x, int y) {	for (int i = 0; i < 8; i++) {		int nx = x + dx[i], ny = y + dy[i];		if (nx < 1 || ny < 1 || nx > n || ny > m || a[nx][ny]) continue;		if (v[nx][ny]) continue;		v[nx][ny] = 1;		if (fx[nx][ny] == 0 || dfs(fx[nx][ny], fy[nx][ny])) {			fx[nx][ny] = x, fy[nx][ny] = y;			return true;		}	}	return false;}int main() {	//freopen("in.txt", "r", stdin);	cin >> n >> m >> t;	for (int i = 0; i < t; ++i) {		int x, y; cin >> x >> y;		a[x][y] = 1;	}	for (int i = 1; i <= n; i++) {		for (int j = 1; j <= m; j++) {			if (i + j & 1) continue;			if (a[i][j]) continue;			memset(v, 0, sizeof(v));			if (dfs(i, j)) ans++;		}	}	cout << n * m - t - ans << endl;}
   

再贴一个网络流的写法 7ms，不得不说匈牙利算法在解决这类问题稍微时间复杂度大了点

#include
   
    using namespace std;#define MAXN 60555#define MAXM 520555int N, M, TT;int hd[MAXN], val[MAXM], nxt[MAXM], to[MAXM], tot(1);int cur[MAXN];int S, T, x, y;bool mp[205][205];void Add( int x, int y, int z ){    nxt[++tot] = hd[x]; hd[x] = tot; to[tot] = y; val[tot] = z;    nxt[++tot] = hd[y]; hd[y] = tot; to[tot] = x; val[tot] = 0;}int d[MAXN]; queue
    
      Q;bool BFS(){    while( !Q.empty() ) Q.pop();    memset( d, 0, sizeof d ); d[S] = 1; Q.push(S);    while( !Q.empty() ){        int t(Q.front()); Q.pop();        for ( int i = hd[t]; i; i = nxt[i] ){            if ( val[i] && !d[to[i]] ){                d[to[i]] = d[t] + 1; Q.push(to[i]);                if ( to[i] == T ) return 1;            }        }    }    return 0;}int DFS( int x, int fl ){    if ( x == T ) return fl;    int res(fl), k;    for ( int &i = cur[x]; i && res; i = nxt[i] ){        if ( val[i] && d[to[i]] == d[x] + 1 ){            k = DFS( to[i], min( res, val[i] ) );            if ( !k ) d[to[i]] = 0;            res -= k; val[i] -= k; val[i ^ 1] += k;        }    }    return fl - res;}int GetID( int x, int y ){ return ( x - 1 ) * M + y; }int dir[][2] = { 1, 2, 2, 1, -1, -2, -2, -1, -1, 2, 2, -1, 1, -2, -2, 1 };int main(){    scanf( "%d%d%d", &N, &M, &TT );    for ( int i = 1; i <= TT; ++i ) scanf( "%d%d", &x, &y ), mp[x][y] = 1;    S = 0; T = N * M + 1;    for ( int i = 1; i <= N; ++i )        for ( int j = 1; j <= M; ++j ){            if ( mp[i][j] ) continue;            if ( ( i ^ j ) & 1 ) Add( S, GetID( i, j ), 1 );            else{                Add( GetID( i, j ), T, 1 );                for ( int k = 0; k < 8; ++k ){                    int tx(i + dir[k][0]), ty(j + dir[k][1]);                    if ( tx > 0 && ty > 0 && tx <= N && ty <= M && !mp[tx][ty] ) Add( GetID( tx, ty ), GetID( i, j ), INT_MAX );                }            }        }    int ans( N * M - TT ), k;    while( BFS() ){        memcpy( cur, hd, sizeof hd );        while( ( k = DFS( S, INT_MAX ) ) ) ans -= k;    }    printf( "%d\n", ans );    return 0;}
    
   

有向无环图的最小路径点覆盖

题目描述

输入

7 51 23 22 44 54 6

输出

3

首先明确，求解的是一个最大的点集，满足集合中的点中任意两个点之间没有通路。ohhhh？？？这不是最大独立集吗？？？可惜这是个有向图，最大独立集也是针对无向图来说的，如果你去找二分图的定义，会发现，前面都有一个前提，一个无向图怎样怎样，也就是说二分图是对无向图而言的。那这个有向图就不能当作最大独立集考虑了。

但是我们知道有向图有最小路径点覆盖，定义如下：选取最少的不相交的边覆盖全部顶点。最小路径可重复覆盖：选取最少可相交的边覆盖全部顶点。对于这个路径的集合，每次从里面最多挑出来一个点，如果挑出来多余一个点，以两个为例，那么这两个点之间肯定有一条简单路径可以连接，也就是说二者肯定有一方可以到达另一方。那么我们从所有的路径中，每个路径挑一个点，最后就组成了这个最大的点集合。

还有一点需要说明，为什么这个问题是一个最小路径可重复覆盖，因为题目中有说，如果一个点沿着某一路径走下去可以到达另一个点，则这两个点也是互相可以望见的，也就是说对于边a->b,b->c，间接的a->c也算。所以就先floyd求一下传递闭包，建立拆点二分图，然后跑一遍DAG最小路径点覆盖。（这类问题博主更习惯于直接用邻接矩阵QAQ）

#include 
   
    #define mem(a, b) memset(a, b, sizeof a)using namespace std;const int N = 210;bool w[N][N];int match[N];bool vis[N];int n, m;bool dfs(int x){	for (int i = 1; i <= n; i++){		if (w[x][i] && !vis[i]){			vis[i] = 1;			if (match[i] == -1 || dfs(match[i])){				match[i] = x;				return 1;			}		}	}	return 0;}void pre_work(){	mem(match, -1);	mem(vis, 0);	for (int k = 1; k <= n; k++){		for (int i = 1; i <= n; i++){			for (int j = 1; j <= n; j++){				w[i][j] = (w[i][k] && w[k][j]) || w[i][j];			}		}	}}int solve(){	int ans = n;	for (int i = 1; i <= n; i++){		mem(vis, 0);		if (dfs(i))ans--;	}	return ans;}int main(){	mem(w, 0);	scanf("%d %d", &n, &m);	for (int i = 1; i <= m; i++){		int x, y;		scanf("%d %d", &x, &y);		w[x][y] = 1;	}	pre_work();	printf("%d\n", solve());	return 0;}