C++算法之旅、06 基础篇 | 第三章 图论
DFS
尽可能往深处搜，遇到叶子节点（无路可走）回溯，恢复现场继续走
- 数据结构：stack
- 空间：需要记住路径上的点，\(O(h)\)。
- ⭐ BFS使用空间少；无最短路性质
每个DFS一定对应一个搜索树；要考虑用什么顺序遍历所有方案；DFS就是递归
剪枝：提前判断当前方案不合法，就不用继续往下走了，直接回溯
842
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 10;
int path[N], n;
bool st[N];
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i++) {
cout << path[i] << " ";
}
cout << endl;
return;
}
for (int i = 1; i <= n; i++) {
if (!st[i]) {
path[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false; // 恢复现场
}
}
}
int main() {
cin.tie(0);
cin >> n;
dfs(0);
return 0;
}
843
搜索顺序、1
每行放一个，直到n行放满，类似全排列
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 20; // 对角线个数 2n-1
char g[N][N];
int n;
bool col[N], dg[N], udg[N];
void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i++) puts(g[i]);
cout << endl;
return;
}
for (int i = 0; i < n; i++) {
if (!col[i] && !dg[u + i] && !udg[n - u + i]) {
g[u][i] = 'Q';
col[i] = dg[u + i] = udg[n - u + i] = true;
dfs(u + 1);
col[i] = dg[u + i] = udg[n - u + i] = false;
g[u][i] = '.';
}
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = '.';
}
}
dfs(0);
return 0;
}
搜索顺序、2
挨个枚举每个格子，每个格子放与不放
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 20; // 对角线个数 2n-1
int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];
void dfs(int x, int y, int s) {
if (y == n) x++, y = 0;
if (x == n) {
if (s == n) {
for (int i = 0; i < n; i++) puts(g[i]);
cout << endl;
}
return;
}
// 不放皇后
dfs(x, y + 1, s);
// 放皇后
if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
g[x][y] = 'Q';
row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
dfs(x, y + 1, s + 1);
row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
g[x][y] = '.';
}
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = '.';
}
}
dfs(0, 0, 0);
return 0;
}
BFS
一层一层搜（稳重）
- 数据结构：queue
- 空间：需要保存一层的点，\(O(2^h)\)
- ⭐ BFS使用空间多；有最短路性质（前提图所有边权重都为 1）
844
d 数组存储每一个点到起点距离
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e2 + 10;
typedef pair<int, int> PII;
int n, m;
int map[N][N], d[N][N];
PII q[N * N];
int bfs() {
int st = 0, ed = 0;
q[0] = {0, 0};
memset(d, -1, sizeof d);
d[0][0] = 0;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
while (st <= ed) {
auto t = q[st++];
for (int i = 0; i < 4; i++) {
int x = t.first + dx[i], y = t.second + dy[i];
if (x >= 0 && x < n && y >= 0 && y < m && map[x][y] == 0 &&
d[x][y] == -1) {
q[++ed] = {x, y};
d[x][y] = d[t.first][t.second] + 1;
}
}
}
return d[n - 1][m - 1];
}
int main() {
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) cin >> map[i][j];
cout << bfs();
return 0;
}
845 ⭐ Airbnb面试
- 状态表示复杂：每个节点相当于3*3矩阵；节点如何存队列里、如何记录距离
- 可以用字符串保存，使用
unordered_map<string,int>
- 可以用字符串保存，使用
- 状态转移
- 想象成3*3的位置；然后把x移动到4个位置上去判断，再恢复成字符串；难点是二维位置与一维位置间的转换
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int bfs(string start) {
string end = "12345678x";
queue<string> q;
unordered_map<string, int> d;
q.push(start);
d[start] = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
while (q.size()) {
auto t = q.front();
q.pop();
int distance = d[t];
if (t == end) return distance;
// 状态转移
int k = t.find('x');
int x = k / 3, y = k % 3;
for (int i = 0; i < 4; i++) {
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < 3 && b >= 0 && b < 3) {
swap(t[k], t[a * 3 + b]);
if (!d.count(t)) {
d[t] = distance + 1;
q.push(t);
}
swap(t[k], t[a * 3 + b]);
}
}
}
return -1;
}
int main() {
cin.tie(0);
string start;
for (int i = 0; i < 9; i++) {
char c;
cin >> c;
start += c;
}
cout << bfs(start) << endl;
return 0;
}
树与图
有向图、无向图 （特殊的有向图，a->b、b->a）。只需要考虑有向图的存储方式。树是无环连通图
邻接矩阵
不太常用。开二维bool数组 G[A][B] 存储 A->B 的信息，有重边就保留一条（可以是最短边）。空间 \(O(n^2)\)，适合存储稠密图
邻接表 ⭐
常用。每个节点上开一个单链表（类似拉链法哈希表），每个链存储可到的点（次序不重要）。单链表可以数组模拟或vector（效率慢），适合存储稀疏图
DFS 树与图
\(O(n+m)\)
846 ⭐⭐
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10; // 数据范围是10的5次方
const int M = 2 * N; // 以有向图的格式存储无向图，所以每个节点至多对应2n-2条边
int h[N]; // 邻接表存储树，有n个节点，所以需要n个队列头节点
int e[M]; // 存储元素
int ne[M]; // 存储列表的next值
int idx; // 单链表指针
int n; // 题目所给的输入，n个节点
int ans = N; // 表示重心的所有的子树中，最大的子树的结点数目
bool st[N]; // 记录节点是否被访问过，访问过则标记为true
// a所对应的单链表中插入b a作为根
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
// dfs 框架
/*
void dfs(int u){
st[u]=true; // 标记一下，记录为已经被搜索过了，下面进行搜索过程
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(!st[j]) {
dfs(j);
}
}
}
*/
// 返回以u为根的子树中节点的个数，包括u节点
int dfs(int u) {
int res = 0; // 存储 删掉某个节点之后，最大的连通子图节点数
st[u] = true; // 标记访问过u节点
int sum = 1; // 存储 以u为根的树 的节点数, 包括u，如图中的4号节点
// 访问u的每个子节点
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
// 因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
if (!st[j]) {
int s = dfs(j); // u节点的单棵子树节点数 如图中的size值
res = max(res, s); // 记录最大联通子图的节点数
sum += s; // 以j为根的树 的节点数
}
}
// n-sum 如图中的n-size值，不包括根节点4；
res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
ans = min(res, ans); // 遍历过的假设重心中，最小的最大联通子图的 节点数
return sum;
}
int main() {
memset(h, -1, sizeof h); // 初始化h数组 -1表示尾节点
cin >> n; // 表示树的结点数
// 题目接下来会输入，n-1行数据，
// 树中是不存在环的，对于有n个节点的树，必定是n-1条边
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a); // 无向图
}
dfs(1); // 可以任意选定一个节点开始 u<=n
cout << ans << endl;
return 0;
}
BFS 树与图
\(O(n+m)\)
847 ⭐
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx, d[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
int bfs() {
memset(d, -1, sizeof d);
queue<int> q;
d[1] = 0;
q.push(1);
while (q.size()) {
auto u = q.front();
q.pop();
int distance = d[u];
if (u == n) return distance;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (d[j] == -1) {
d[j] = distance + 1;
q.push(j);
}
}
}
return -1;
}
int main() {
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs();
return 0;
}
有向图的拓扑序列
拓扑序列：有向边uv， u在序列中都在v之前
有向无环图被称为拓扑图。有向无环图至少存在一个入度为0的点，所有入度0的点排在最前位置，然后不断删除入度为0的点
848 ⭐
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], ne[N], e[N], idx, d[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void bfs() {
queue<int> q;
queue<int> ans;
for (int i = 1; i <= n; i++) {
if (!d[i]) q.push(i);
}
while (q.size()) {
auto u = q.front();
ans.push(u);
q.pop();
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
d[j]--;
if (d[j] == 0) q.push(j);
}
}
if (ans.size() != n)
cout << -1;
else
while (ans.size()) {
cout << ans.front() << " ";
ans.pop();
}
}
int main() {
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
d[b]++;
}
bfs();
return 0;
}
最短路
- 单源最短路：单个点到其他所有点最短距离。 （n 点数，m 边数）
- 所有边权都是正数
- 朴素Dijkstra：\(O(n^2)\) 适用于稠密图
- 堆优化版Dijkstra：\(O(mlog_2n)\) 适用于稀疏图
- 存在负权边
- 贝尔曼-福特 Bellman-Ford：\(O(nm)\)
- 优化贝尔曼-福特 SPFA：一般\(O(m)\)，最坏\(O(nm)\)
- 所有边权都是正数
- 多源汇最短路：起点与终点不确定（一对起点终点）
- 弗洛伊德 Floyd：\(O(n^3)\)
⭐ 考察侧重点是建图，定义点和边
朴素Dijkstra
利用了贪心，每次找最小的
-
初始化所有点到起点距离：dis[1] = 0，dis[i] = +∞
-
集合s：存储已经确定最短距离的点
-
for n次
-
找到不在 s 中的距离原点最近的点 t
-
t 加到 s 去
-
用 t 更新其他点的距离（从t出去所有边能否更新其他点距离）
dis[x] > dis[t] + w
-
849
849. Dijkstra求最短路 I - AcWing题库
稠密图，用邻接矩阵存；最短路问题里面，自环应不存在，重边应只保留距离最短的
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra() {
// 初始化
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
// 路径最长n个点
for (int i = 1; i <= n; i++) {
// 寻找不在s中的dist最小的点t
int t = -1;
for (int i = 1; i <= n; i++) {
if (!st[i] && (t == -1 || dist[t] > dist[i])) t = i;
}
// 将t加入s
st[t] = true;
// 更新 dist
for (int i = 1; i <= n; i++) {
// if (g[t][i] != 0x3f3f3f3f) {
dist[i] = min(dist[i], dist[t] + g[t][i]);
// }
}
}
if (dist[n] == 0x3f3f3f3f)
return -1;
else
return dist[n];
}
int main() {
cin.tie(0);
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m--) {
int a, b, c;
cin >> a >> b >> c;
// 解决 自环、重边 问题
if (a != b) g[a][b] = min(g[a][b], c);
}
int t = dijkstra();
cout << t << endl;
return 0;
}
堆优化Dijkstra
朴素方法中，查找不在 s 中距离原点最近的点共执行 \(n^2\) 次；更新dis数组相当于遍历了所有边，共执行 m 次；**可以对这两个操作进行堆优化，前者变\(O(1)*O(n)=O(n)\)，后者变\(O(log_2n)*O(m)=O(mlog_2n)\) **
堆有两种实现方式：手写堆、优先队列（不支持修改任意一个元素操作，容易冗余）
前者有n个元素，后者可能m个元素；使用优先队列时间复杂度可能变成\(O(mlog_2m)\)
\(log_2m <= log_2n^2 = 2log_2n\) 两者是一个级别的，可以不用手写堆
851 ⭐
稀疏图，用邻接表存；
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1.5e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx, w[N], dist[N];
bool st[N];
typedef pair<int, int> PII;
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int dijkstra() {
// 初始化
priority_queue<PII, vector<PII>, greater<PII>> heap;
memset(dist, 0x3f, sizeof dist);
heap.push({0, 1});
dist[1] = 0;
while (heap.size()) {
// 查找t O(logn)
auto t = heap.top();
heap.pop();
int ver = t.second, distance = t.first;
if (st[ver]) continue;
st[ver] = true;
// 更新堆 O(m)
for (int i = h[ver]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
heap.push({w[i] + t.first, j});
}
}
}
return dist[n] != 0x3f3f3f3f ? dist[n] : -1;
}
int main() {
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
cout << dijkstra() << endl;
return 0;
}
Bellman-Ford
结构体存 a,b,w 然后开个数组；执行后满足任意边 dist[b] <= dist[a] + w （三角不等式）
- for n次
- for 所有边 a,b,w
- dist[b] = min(dist[b],back[a]+w) （松弛操作）
- for 所有边 a,b,w
- back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点
1到n的路径上有负权回路的话，最短路不存在（而spfa要求图中不能有任何负环）
迭代k次相当于从原点经过不超过k条边走到每个点的最短距离；该算法可以用于判断负环
853
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N], backup[N];
struct Edge {
int a, b, w;
} edges[M];
int bellman_ford() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < k; i++) {
// IMPORTANT 避免串联
memcpy(backup, dist, sizeof dist);
for (int j = 0; j < m; j++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
dist[b] = min(dist[b], backup[a] + w);
}
}
// IMPORTANT 避免 5-(-2)->n 的情况
if (dist[n] > 0x3f3f3f3f / 2)
return 0x3f3f3f3f;
else
return dist[n];
}
int main() {
cin.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
int t = bellman_ford();
if (t == 0x3f3f3f3f)
puts("impossible");
else
cout << t;
return 0;
}
SPFA
必须图里没有负环，99%的最短路问题没有负环。用宽搜优化贝尔曼-福特算法
- 队列里存所有需要变小的节点，然后宽搜
851 ⭐
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1.5e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx, w[N], dist[N];
bool st[N];
typedef pair<int, int> PII;
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
int spfa() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
if (dist[n] == 0x3f3f3f3f)
return 0x3f3f3f3f;
else
return dist[n];
}
int main() {
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
int t = spfa();
if (t == 0x3f3f3f3f)
puts("impossible");
else
cout << t;
return 0;
}
852 ⭐
cnt 数组维护原点到各点的边数，如果 cnt[x] >= n 则有负环；注意一开始需要把所有点放入
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 1.5e5 + 10;
int n, m;
int h[N], e[N], ne[N], idx, w[N], dist[N], cnt[N];
bool st[N];
typedef pair<int, int> PII;
void add(int a, int b, int c) {
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
bool spfa() {
// memset(dist, 0x3f, sizeof dist);
// dist[1] = 0;
queue<int> q;
for (int i = 1; i <= n; i++) {
q.push(i);
st[i] = true;
}
while (q.size()) {
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i];
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if (cnt[j] >= n) return true;
if (!st[j]) {
q.push(j);
st[j] = true;
}
}
}
}
return false;
}
int main() {
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
}
if (spfa())
puts("Yes");
else
puts("No");
return 0;
}
Floyed
- 邻接矩阵 d
- for k=1 k<=n k++
- for i=1 i<=n i++
- for j=1 j<=n j++
- d(i,j) = min(d(i,j),d(i,k)+d(k,j))
- for j=1 j<=n j++
- for i=1 i<=n i++
基于DP，k,i,j 从 i 点出发只经过 1~k 中间点到达 j 的最短距离
854
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 210;
int n, m, Q;
int d[N][N];
void floyed() {
for (int k = 1; k <= n; k++)
for (int j = 1; j <= n; j++)
for (int i = 1; i <= n; i++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main() {
cin.tie(0);
cin >> n >> m >> Q;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i == j)
d[i][j] = 0;
else
d[i][j] = 0x3f3f3f3f;
while (m--) {
int a, b, w;
cin >> a >> b >> w;
d[a][b] = min(d[a][b], w);
}
floyed();
while (Q--) {
int a, b;
cin >> a >> b;
if (d[a][b] > 0x3f3f3f3f / 2)
puts("impossible");
else
cout << d[a][b] << endl;
}
return 0;
}
最小生成树
最小生成树问题99%对应的图都是无向图，正边和负边都可以
- 普利姆算法 Prim
- 朴素版Prim \(O(n^2)\) 稠密图
- 堆优化Prim \(O(mlog_2n)\) 稀疏图，不常用
- 克鲁斯卡尔算法 Kruskal \(O(mlog_2m)\) 稀疏图，常用
Prim
与Dijkstra非常类似，不同的是用 t 更新其他点到集合s的距离，而不是其他点到原点的距离。集合s是当前已经在集合中的点；不在集合内的点，每个点连向集合的边的最短距离，无边为INF
最小生成树的边就是选中 t 时，t 与 集合s之间的边。
858
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 510, INF = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int prim() {
memset(dist, 0x3f, sizeof dist);
int res = 0;
for (int i = 0; i < n; i++) {
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
if (i && dist[t] == INF) return INF;
if (i)
res +=
dist[t]; // ^ 在更新 dist 之前累加，因为有自环问题（-10权重）
for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
st[t] = true;
}
return res;
}
int main() {
cin.tie(0);
cin >> n >> m;
memset(g, 0x3f, sizeof g);
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
g[a][b] = g[b][a] = min(g[a][b], w);
}
int t = prim();
if (t == INF)
puts("impossible");
else
cout << t;
return 0;
}
Kruskal
不需要用邻接表或邻接矩阵存图，只要存每条边（结构体数组）
- 将所有边ab按w重小到大排序（快排）\(O(mlog_2m)\)
- 枚举每条边ab w （相当于并查集简单应用 \(O(m)\)）
- 如果ab不连通，将ab加到集合里面来
859 ⭐
AcWing 859. Kruskal算法求最小生成树 - AcWing
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int n, m;
int p[N];
struct Edge {
int a, b, w;
bool operator<(const Edge &W) const { return w < W.w; }
} edges[N];
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int a, b, w;
cin >> a >> b >> w;
edges[i] = {a, b, w};
}
sort(edges, edges + m);
// ^ 初始化并查集
for (int i = 1; i <= n; i++) p[i] = i;
int res = 0, cnt = 0;
for (int i = 0; i < m; i++) {
int a = edges[i].a, b = edges[i].b, w = edges[i].w;
a = find(a), b = find(b);
if (a != b) {
p[a] = b;
res += w;
cnt++;
}
}
if (cnt < n - 1)
puts("impossible");
else
cout << res;
return 0;
}
二分图
- 判断是否二分图：DFS 染色法 \(O(n+m)\)
- 求二分图最大匹配：匈牙利算法 最坏\(O(nm)\)，实际运行时间远小于\(O(nm)\)
染色法
二分图：把所有点划分成两个集合，集合内没有边，集合之间有边；当且仅当图中不含奇数环（环中边的数量是奇数）
可以用 DFS、BFS 模拟染色过程，出现矛盾就不是二分图
860
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m;
int h[N], e[M], ne[M], idx;
int color[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool dfs(int u, int c) {
color[u] = c;
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!color[j]) {
if (!dfs(j, 3 - c)) return false;
} else if (color[j] == c)
return false;
}
return true;
}
int main() {
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m;
while (m--) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
bool flag = true;
for (int i = 1; i <= n; i++) {
if (!color[i]) {
if (!dfs(i, 1)) {
flag = false;
break;
}
}
}
if (flag)
puts("Yes");
else
puts("No");
return 0;
}
匈牙利
返回二分图最大匹配（最多的边数，没有两条边共用一个点）
861
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 510, M = 1e5 + 10;
int n1, n2, m;
int h[N], e[M], ne[M], idx;
int match[N];
bool st[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
bool find(int x) {
for (int i = h[x]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true;
if (match[j] == 0 || find(match[j])) {
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n1 >> n2 >> m;
while (m--) {
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
for (int i = 1; i <= n1; i++) {
memset(st, false, sizeof st);
if (find(i)) res++;
}
cout << res;
return 0;
}
372 ⭐⭐
每个卡片塞2个格子，把格子看成点，把卡片看成边，则只要能放卡片的相邻两个格子就连一条边。考虑卡片不会重叠，一定是一个二分图。
二分图最大匹配：匈牙利算法 (男女配对算法 我有多的选择就让给你 你有多的选择就让给我)
#include <cstring>
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int n, m;
PII match[N][N];
bool g[N][N], st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// dfs
bool find(int x, int y)
{
for (int i = 0; i < 4; i ++ )//枚举邻点
{
int a = x + dx[i], b = y + dy[i];
if (a && a <= n && b && b <= n && !g[a][b] && !st[a][b])//不是坏点 没遍历过
{
// 则男[x,y] 和 女[a,b]能够配对
st[a][b] = true;
PII t = match[a][b];//
//1 t.x==-1说明女[a,b]还没和其他人配对 则男[x,y]和女[a,b]可以直接配对
//2 女[a,b]已经有人配对,但和女[a,b]配对的男t还有其他选项
// 男t放弃和女[a,b]配对 让女[a,b]给男[x,y]配对(我感动了)
if (t.x == -1 || find(t.x, t.y))
{
match[a][b] = {x, y};
return true;
}
}
}
return false;
}
int main()
{
cin >> n >> m;
while(m--)
{
int x,y;
cin >> x >> y;
g[x][y] = true;
}
memset(match,-1,sizeof match);
int res = 0;
// 枚举所有和为奇数的点
for(int i=1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
if((i+j)%2 && !g[i][j])
{
memset(st,0,sizeof st);//每次都需要清空st数组，因为匹配好的一对可能会有下家
if(find(i,j))res++;//如果[i,j]能配对
}
}
}
cout << res << endl;
return 0;
}