参考资料:acwing,算法竞赛进阶指南
主要内容:二分图,二分图的匹配,最小点覆盖和最大独立集
如果一个无向图中有N个节点(N >= 2)可以分成A, B两个非空集合,其中A ∩ B = Ø,并且在同一个集合内的点之间都没有边相连,那么称这张无向图为一张二分图,A, B 分别成为二分图的左部和右部
定理:如果一张图是二分图,当且仅当图中不存在长度为奇数的环
二分图的染色和判断(点数为n)
bool dfs(int u, int c)
{
color[u] = c;
for (auto i : e[u])
{
if (!color[i] && !dfs(i, 3 - c)) return false;
else if (color[i] != 3 - c) return false;
}
return true;
}
bool check()
{
for (int i = 1; i <= n; i ++)
if (!color[i] && !dfs(i, 1)) return false;
return true;
}
例题 acwing 257关押罪犯
我们令市长看到的最大冲突指数为x,也就是说对于x以上冲突指数的两人我们要把他们分开,对于x及它以下冲突指数的两人我们不用管,我们不难发现x越大,说明条件约束越小,因此答案具有单调性,如果在x时可以构成一个二分图,说明x右边也都可以构成二分图,那么我们让r = mid,否则l = mid + 1
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 20010;
vector<PII> e[N];
int n, m;
bool check(int limit)
{
vector<int> color(N, 0);
for (int i = 1; i <= n; i ++)
{
if (!color[i])
{
function<bool(int, int)> dfs = [&](int u, int c)
{
color[u] = c;
for (auto i : e[u])
{
if (i.second <= limit) continue;
if (!color[i.first] && !dfs(i.first, 3 - c)) return false;
else if (color[i.first] && color[i.first] != 3 - c) return false;
}
return true;
};
if (!dfs(i, 1)) return false;
}
}
return true;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i ++)
{
int u, v, w; cin >> u >> v >> w;
e[u].push_back({v, w});
e[v].push_back({u, w});
}
int l = 0, r = 1e9;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
二分图的最大匹配
概念:“任意两条边都没有公共的端点”的边的集合叫做二分图的一组匹配,在二分图中包含边数最多的一组匹配叫二分图的最大匹配
用NTR算法找二分图的最大匹配(也称匈牙利算法和找对象算法,比较规范的叫法应该是增广路算法)
bool find(int x)
{
for (int i : e[x])
{
if (!st[i])
{
st[i] = true;
if (!match[i] || find(match[i]))
{
match[i] = x;
return true;
}
}
}
return false;
}
int check()
{
int ans = 0;
for (int i = 1; i <= n1; i ++)
{
memset(st, false, sizeof st);
if (find(i)) ans ++;
}
return ans;
}
二分图匹配的模型有两个要素:1.节点能分成独立的两个集合,每个集合内部有0条边,2.每个节点只能与1条匹配边相连
例题 acwing 372棋盘覆盖
对于这题而言,0要素,即将所有横坐标纵坐标之和为奇数的点和所有横纵坐标为偶数的点分为两个集合A,B,骨牌不能斜着摆放,所以A或者B中的点内部不会有连线,1要素,骨牌不能重叠摆放,因此每个节点只会有一条边
#pragma GCC optimize(2)
#include <iostream>
#include <vector>
#include <functional>
#include <cstring>
using namespace std;
const int N = 110, M = N * N;
vector<int> e[M / 2];
int match[M / 2];
int g[N][N], r[N][N], n1, n2, ans;
bool st[M / 2];
int n, m;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i ++)
{
int x, y; cin >> x >> y;
g[x][y] = 1;
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (!g[i][j] && (i + j) & 1) r[i][j] = ++ n1;
else if (!g[i][j]) r[i][j] = ++ n2;
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
{
if (!g[i][j] && (i + j) & 1)
{
for (int k = 0; k < 4; k ++)
{
int x = dx[k] + i, y = dy[k] + j;
if (x < 1 || x > n || y < 1 || y > n || g[x][y]) continue;
else e[r[i][j]].push_back(r[x][y]);
}
}
}
function<bool(int)> find = [&](int x)
{
for (int i : e[x])
{
if (!st[i])
{
st[i] = true;
if (!match[i] || find(match[i]))
{
match[i] = x;
return true;
}
}
}
return false;
};
for (int i = 1; i <= n1; i ++)
{
memset(st, false, sizeof st);
if (find(i)) ans ++;
}
cout << ans << endl;
return 0;
}
acwing 373车的摆放
对于这题而言,0要素是行和列,如果车摆在i行j列上,那么我们视为i,j连一条边,车只能在指定的一行或者一列上,不能说这个车会分身他又在这行又在那行,所以行和列的集合中不会存在内部连边,1要素是如果第i行第j列放了一个车,那么i行j列就不能再放车了,因此每个节点只会有一条对应的边
#include <iostream>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
const int N = 210;
vector<int> e[N];
int g[N][N];
bool st[N];
int match[N];
int main()
{
int n, m, k; cin >> n >> m >> k;
for (int i = 0; i < k; i ++)
{
int x, y; cin >> x >> y;
g[x][y] = 1;
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
if (!g[i][j]) e[i].push_back(j);
function<bool(int)> find = [&](int x)
{
for (int i : e[x])
{
if (!st[i])
{
st[i] = true;
if (!match[i] || find(match[i]))
{
match[i] = x;
return true;
}
}
}
return false;
};
int ans = 0;
for (int i = 1; i <= n; i ++)
{
memset(st, false, sizeof st);
if (find(i)) ans ++;
}
cout << ans << endl;
return 0;
}
acwing 374导弹防御塔
对这题而言,0要素是导弹和敌人,导弹不会互相攻击,敌人不会自相残杀,因此将导弹集合视为A,敌人集合视为B,1要素是每个导弹只能打一个敌人,每个敌人也只能被一个导弹消灭,因此每个节点只会被一条边相连
时间越多肯定是越有可能消灭敌人,因此我们可以使用二分进行优化如果发现B中的所有点都被匹配了,就说明时间足够消灭敌人,令r = mid否则l = mid(注意这里一定要选择B作为检查的点集,不是每颗导弹被匹配了就可以了,是要每个敌人都被消灭才可以)
同时这里坑点很多:首先要算出每个塔到每个敌人之间的距离,导弹打过去还需要dist / v的时间,超过了就不能连边了,其次每个塔在mid的时间内最多发射min(m, (mid + t2) / (t1 + t2))发导弹,第三,t1是秒数不是分钟
#pragma GCC optimize(2)
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <functional>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 60;
const double eps = 1e-9;
PII enemy[N], tower[N];
double dist[N][N];
bool st[N * N];
double get_dist(int i, int j)
{
double k1 = enemy[i].x - tower[j].x, k2 = enemy[i].y - tower[j].y;
return sqrt(k1 * k1 + k2 * k2);
}
int main()
{
int n, m; cin >> n >> m;
double t1, t2, v; cin >> t1 >> t2 >> v;
t1 /= 60;
for (int i = 1; i <= m; i ++) cin >> enemy[i].x >> enemy[i].y;
for (int i = 1; i <= n; i ++) cin >> tower[i].x >> tower[i].y;
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++)
dist[i][j] = get_dist(i, j);
double l = 0, r = 1e9;
while (r - l > eps)
{
double mid = (l + r) / 2;
int cnt = (mid + t2) / (t1 + t2);
cnt = min(m, cnt);
vector<int> e[m + 10], match(cnt * n + cnt + 10, 0);
for (int i = 1; i <= m; i ++)
for (int j = 1; j <= n; j ++)
for (int k = 1; k <= cnt; k ++)
if (k * t1 + (k - 1) * t2 + dist[i][j] / v < mid) e[i].push_back(j * cnt + k);
function<bool(int)> find = [&](int x)
{
for (auto i : e[x])
{
if (!st[i])
{
st[i] = true;
if (!match[i] || find(match[i])) { match[i] = x; return true;}
}
}
return false;
};
function<bool()> check = [&]()
{
for (int i = 1; i <= m; i ++)
{
memset(st, false, sizeof st);
if (!find(i)) return false;
}
return true;
};
if (check()) r = mid;
else l = mid;
}
printf("%.6lf", l);
return 0;
}
带权匹配: 太难了,网络流再见
二分图的最小点覆盖
给定一个二分图,求出最小的点集S,使得图中任意一条边都有至少一个点属于S,这个问题被称为二分图的最小点覆盖问题,简称最小覆盖
结论:二分图的最小点覆盖包含的点数等于二分图的最大匹配包含的边数
对于最小覆盖模型,如果有2要素,即每条边有两个端点,必须选择一个,可以尝试抽象成二分图解决
acwing 376机器任务
对于这题而言,2要素都非常明显,求最小重启数量就是求二分图的最小点覆盖
#pragma GCC optimize(2)
#include <iostream>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
const int N = 110;
bool st[N];
int n, m, k;
int main()
{
ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
while (cin >> n, n)
{
cin >> m >> k;
vector<int> e[n + 1];
while (k --)
{
int op, u, v; cin >> op >> u >> v;
if (!u || !v) continue;
e[u].push_back(v);
}
int ans = 0;
vector<int> match(m + 1, -1);
function<bool(int)> find = [&](int x)
{
for (int i : e[x])
{
if (!st[i])
{
st[i] = true;
if (match[i] == -1 || find(match[i]))
{
match[i] = x;
return true;
}
}
}
return false;
};
for (int i = 0; i < n; i ++)
{
memset(st, 0, sizeof st);
if (find(i)) ans ++;
}
cout << ans << endl;
}
return 0;
}
acwing 377泥泞的路径
由于板子不能盖住干净的地面,所以假设所有板子都横着放,构造出第一种情况,所有板子都竖着放,构造出第二种情况,对于每个有泥土的点而言都必须被覆盖,因此符合2,尝试用最小点覆盖解决
#include <iostream>
#include <vector>
#include <cstring>
#include <functional>
using namespace std;
const int N = 60, M = N * N;
vector<int> e[M];
char g[N][N];
int a[N][N], b[N][N];
bool st[M];
int match[M];
int n1 = 1, n2 = 1;
int main()
{
int n, m; cin >> n >> m;
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++) cin >> g[i][j];
bool flag = false;
for (int i = 0; i < n; i ++)
{
for (int j = 0; j < m; j ++)
{
if (!flag && g[i][j] == '*') a[i][j] = ++ n1, flag = true;
if (flag && g[i][j] == '*') a[i][j] = n1;
else flag = false;
}
flag = false;
}
flag = false;
for (int j = 0; j < m; j ++)
{
for (int i = 0; i < n; i ++)
{
if (!flag && g[i][j] == '*') b[i][j] = ++ n2, flag = true;
if (flag && g[i][j] == '*') b[i][j] = n2;
else flag = false;
}
flag = false;
}
for (int i = 0; i < n; i ++)
for (int j = 0; j < m; j ++)
if (g[i][j] == '*') e[a[i][j]].push_back(b[i][j]);
function<bool(int)> find = [&](int x)
{
for (int i : e[x])
{
if (!st[i])
{
st[i] = true;
if (!match[i] || find(match[i]))
{
match[i] = x;
return true;
}
}
}
return false;
};
int ans = 0;
for (int i = 1; i <= n1; i ++)
{
memset(st, false, sizeof st);
if (find(i)) ans ++;
}
cout << ans << endl;
return 0;
}
二分图的最大独立集
通俗的来讲:图的独立集就是任意两点之间都没有边相连,包含点数最多的点集就是最大独立集
对应的,任意两点之间都有一条边相连的子图被称为无向图的团。点数最多的团被称为最大团
定理:无向图G的最大团等于其补图的最大独立集
补图:将G补成完全图后再将G去掉得到的图即补图
下面给出补图例子(注意节点不能漏)
定理:设G是由n个节点的二分图,G的最大独立集的大小等于n减去最大匹配数
acwing 378骑士放置
先对格子黑白染色,同棋盘摆放,不难发现会攻击到彼此的骑士会处在不同颜色的格子中,因此这是一个二分图,接下来求该图的最大独立集即可(任意两点不能有边,否则会攻击到彼此)
#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m, k;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
bool find(int x, int y)
{
for (int i = 0; i < 8; i ++ )
{
int a = x + dx[i], b = y + dy[i];
if (a < 1 || a > n || b < 1 || b > m) continue;
if (g[a][b]) continue;
if (st[a][b]) continue;
st[a][b] = true;
PII t = match[a][b];
if (t.x == 0 || find(t.x, t.y))
{
match[a][b] = {x, y};
return true;
}
}
return false;
}
int main()
{
cin >> n >> m >> k;
for (int i = 0; i < k; i ++ )
{
int x, y;
cin >> x >> y;
g[x][y] = true;
}
int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
if (g[i][j] || (i + j) % 2) continue;
memset(st, 0, sizeof st);
if (find(i, j)) res ++ ;
}
cout << n * m - k - res << endl;
return 0;
}
最小路径覆盖
概念:给定一张有向无环图,要求用尽量少的不相交的简单路径,覆盖有向无环图的所有顶点(也就是每个顶点被恰好覆盖一次)
定理:有向无环图的最小路径覆盖数等于n减去拆点之后的二分图G2的最大匹配数