二分图

“远方那是什么？“

”是荒野。“ 鼹鼠说。

”别害怕它。“

”想象一下，如果我们不那么恐惧，会变成什么样？“

二分图：可以把所有的点分成两个集合，集合内部的点没有边相连，只有不同集合的点才有边相连。

二分图判定与染色

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline int rd() {
	int x = 0;
	bool f = 0;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) f |= (c == '-');
	for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
	return f ? -x : x;
}

#define N 200007
int bl[N];
vector<int> e[N];

bool dfs(int u) {
	for (auto v : e[u]) {
		if (~bl[v]) {
			bl[v] = bl[u] ^ 1;
			if (!dfs(v)) return false;
		} else {
			if (bl[u] == bl[v]) return false;
		}
	}
	return true;
}

inline void add(int u, int v) {e[u].push_back(v); e[v].push_back(u);}

inline void work() {
	int n = rd(), m = rd();
	for (int i = 1; i <= n; ++i) {e[i].clear(); bl[i] = -1;}
	for (int i = 1; i <= m; ++i) {
		int u = rd(), v = rd();
		add(u, v); add(v, u);
	}
	for (int i = 1; i <= n; ++i)
		if (~bl[i]) {
			bl[i] = 0;
			if (!dfs(i)) {puts("NO"); return;}
		}
	puts("YES");
}

int main() {
	for (int t = rd(); t; --t) work();
	return 0;
}

二分图最大匹配

二分图最大匹配是指，让匹配上的点尽可能多。

思路：把边看成有向边，从左边指向右边，给左边的点建立邻接表，右面的点开一个数组，记，每一个点与左面的哪个点进行匹配。扫描左边的每一个点，尝试匹配。尝试匹配的过程开一个数组，表示在尝试更新当前点的时候，已经试过和左边的这个点进行交换，这样子可以避免环的情况，如上图中，左边第一、三个点和右面两个点会形成一个循环。

洛谷P3386 洛谷P1894 洛谷P2756

模板题，求最大匹配。

#define N 507

vector<int> e[N];
bool vis[N];
int match[N];

bool dfs(int u) {
    for (auto v : e[u])
        if (!vis[v]) {
            vis[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = u; return true;
            }
        }
    return false;
}

int main() {
    int n = rd(), m = rd(); m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd();
        e[u].push_back(v);
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        memset(vis, 0, sizeof(vis));
        ans += dfs(i);
    }
    printf("%d\n", ans);
    return 0;
}

洛谷P2071

有排座位，个人，每个人有自己喜欢的排，每排有两个座位，问有多少个人能做到自己喜欢的排。

思路：

拆点，把一排拆成两个点。和
数组和数组开成两维。

#define N 2007

vector<int> e[N * 2];
bool vis[N][2];
int match[N][2];

bool dfs(int u) {
    for (auto v : e[u]) {
        if (!vis[v][0]) {
            vis[v][0] = 1;
            if (!match[v][0] || dfs(match[v][0])) {match[v][0] = u; return true;}
        }
        if (!vis[v][1]) {
            vis[v][1] = 1;
            if (!match[v][1] || dfs(match[v][1])) {match[v][1] = u; return true;}
        }
    }
    return false;
}

int main() {
    int n = rd();
    for (int i = 1; i <= 2 * n; ++i) {
        for (int j = 1; j <= 2; ++j) {
            int v = rd(); e[i].push_back(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= 2 * n; ++i) {
        memset(vis, 0, sizeof(vis));
        ans += dfs(i);
    }
    printf("%d\n", ans);
    return 0;
}

洛谷P1129

给一个的矩阵，问能否通过行交换和列交换，使得对角线上的位置，都是。

思路：等价于这个矩阵是否满秩，也就是是否每一行都能找到一个主元位置。把行抽象成左边的点，列抽象成右边的点，等价于最大匹配是否等于。

#define N 207

vector<int> e[N];
bool vis[N];
int match[N];

bool dfs(int u) {
    for (auto v : e[u])
        if (!vis[v]) {
            vis[v] = 1;
            if (!match[v] || dfs(match[v])) {
                match[v] = u; return true;
            }
        }
    return false;
}

inline void work() {
    memset(match, 0, sizeof(match));
    int n = rd();
    for (int i = 1; i <= n; ++i) e[i].clear();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            int c = rd();
            if (c) e[i].push_back(j);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        memset(vis, 0, sizeof(vis));
        ans += dfs(i);
    }
    if (ans == n) puts("Yes");
    else puts("No");
}

int main() {
    for (int t = rd(); t; --t) work();
    return 0;
}