【算法笔记】图论基础（二）：最短路、判环、二分图

---

最短路

松弛操作

很多最短路算法和最小生成树的算法都涉及到一个操作叫松弛操作，那什么叫松弛操作呢？

• 考虑节点u以及它的邻居v，从起点跑到v有好多跑法，有的跑法经过u，有的不经过。
• 经过u的跑法的距离就是 dist[u] + u到v的距离。
• 所谓松弛操作，就是看一看 dist[v] 和 dist[u] + u到v的距离 哪个大一点。
• 如果前者大一点，就说明当前的不是最短路，就要赋值为后者，这就叫做松弛。

举一个最经典的例子：如果dist[i]表示某个点到点i的最短距离，而对于此时的一条边u -> v边权为w:

if(dist[v] > dist[u] + w)dist[v] = dist[u] + w;

或者直接写成

dist[v] = min(dist[v], dist[u] + w);

这就是对u -> v 的一次松弛操作

Dijkstra

Dijkstra算法和求最小生成树的Prim算法思路相同，也是将所有的点划分成两个区间，然后n次迭代，不断地向连通部分中加点，不同的是Dijkstra的“连通部分”表示的是已经确定最短路径的点（dist已经更新为到源点的最短距离的点）

注意： Prim中的dist[i]表示的是i距离连通部分的最短距离，Dijkstra中的dist[i]表示的是i距离源点的最短距离，别弄混了，

朴素Dijkstra

时间复杂度

$O(n^2)$，适合n较小的稠密图，并且只能处理正权图

算法过程

1. 将所有点的dist初始化成正无穷（因为后面要取min）
2. 将源点的dist赋值成0（源点到源点的最短距离为0）
3. 接下来每次迭代，遍历所有没确定最短距离的点，找到离源点最近（dist最小）的点，此时的dist就是最短距离，标记一下已确定其最短距离。
4. 用该点对其他所有点进行松弛，更新其他点的dist
5. 继续下一次迭代，直到所有点都确定好最短路（由于一次加一个点，所以n个点只需迭代n 次）
6. dist[x]即你要求的点x到源点的最短路

例题

Dijkstra求最短路 I

因为是稠密图，所以适合用邻接矩阵存图

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 505;int n, m;
int g[N][N]; // 邻接矩阵存图
int dist[N]; // dist[i]表示当前i离源点的最短距离
bool st[N]; // st标记当前点是否已经确定最短路，st[i] = true说明已经确定了，st[i] = false说明还没确定int dijkstra(){memset(dist, 0x3f, sizeof dist); // 一开始，初始化所有点到源点最短距离为正无穷memset(st, false, sizeof st); // 一开始，所有点都没确定最短路dist[1] = 0; // 源点到源点的最短距离为0for(int i = 0; i < n; i++){ // 迭代n次int t = -1; // t来记录未确定的点中距离源点最近的点for(int j = 1; j <= n; j++){ // 遍历所有未确定最短路的点, 找到离源点最近的点if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // t == -1:防止越界; dist[t] > dist[j]：点j比点t离源点近}st[t] = true; // t已经确定了距距离源点的最短距离for(int j = 1; j <= n; j++){ // 遍历所有点，对其他没确定的点进行松弛dist[j] = min(dist[j], dist[t] + g[t][j]);}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;memset(g, 0x3f, sizeof g); // 由于要取min，所以初始化成正无穷while(m--){int a, b, c;cin >> a >> b >> c;g[a][b] = min(g[a][b], c); // 求最短路，如果有重边就只要最短边}cout << dijkstra() << endl;return 0;
}

堆优化Dijkstra

时间按复杂度

$O(mlogn)$ ，适合稀疏图，并且只能处理正权图。

算法过程

和朴素版Dijkstra相同，就是迭代的过程用优先队列替代了双重for循环，每次就可以用log级别的复杂度找到当前没确定最短路的距离源点最近的点（堆顶）

例题

Dijkstra求最短路 II

因为是稀疏图，所以适合用邻接表存图

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;int n, m;
vector<PII> g[N]; // 邻接表存图
int dist[N]; // dist[i]表示当前i离源点的最短距离
bool st[N]; // st标记当前点是否已经加入连通部分，st[i] = true说明已经加入了，st[i] = false说明还没加入int dijkstra(){memset(dist, 0x3f, sizeof dist); // 一开始，连通部分中没有点，所有点到源点最短距离为正无穷memset(st, false, sizeof st); // 一开始，连通部分中没有点priority_queue<PII, vector<PII>, greater<PII>> q; // 优先队列-小跟堆dist[1] = 0; // 源点到源点的最短距离为0q.push({0, 1}); // 将源点入队，用源点松弛其他的点while(!q.empty()){auto t = q.top(); // 小跟堆的堆顶就是dist最小的点，就是距离源点最近的点q.pop(); int ver = t.second; // 距离源点最近的点if(st[ver]) continue; // 如果已经确定过最短距离，说明已经用这个点松弛过其他的点了，再松驰一遍就没意义了，直接continuest[ver] = true; // ver已经确定了距距离源点的最短距离for(auto i : g[ver]){ // 遍历ver的所有出边，对ver的所有临点进行松弛if(dist[i.first] > dist[ver] + i.second){ // 松弛操作dist[i.first] = dist[ver] + i.second;q.push({dist[i.first], i.first}); // 松弛完了这个点的dist就变了，将这个点入队，用新的dist去松弛其他点}}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;while(m--){int a, b, c;cin >> a >> b >> c;g[a].push_back({b, c});}cout << dijkstra() << endl;return 0;
}

注意：Dijkstra算法优先队列如果用pair<int, int> 的话，一定要把dist放在第一维，因为pair排序是优先按第一维排，第一维相等再按第二维排的。

bellman-ford

时间复杂度

$O(nm)$，效率很低，基本不会用，但可以处理负权边，并且可以求有边数限制的最短路。

为什么dijkstra不能处理负权边？

dijkstra的三个步骤：

• 找到当前未标识的且离源点最近的点t
• 对t进行标识
• 用t更新其他点的距离

反例

Dijkstra算法在图中走出来的最短路径是1 -> 2 -> 4 -> 5，算出 1 号点到 5 号点的最短距离是2 + 2 + 1 = 5
然而还存在一条路径是1 -> 3 -> 4 -> 5，该路径的长度是5 + (-2) + 1 = 4，因此 Dijkstra 算法失效

失效的原因

Dijkstra算法是基于贪心的思想去不断迭代来找最短路，每一步看的都是当前的最优解，比如现在dist[2] = 2, dist[3] = 5，如果都是正权边的话，后面经过3到达的点距离1的距离一定是dist[3]加上一个正数，只会更大不会更小，即dist[3] + w > dist[3] > dist[2]，所以选择走2这个局部最优解也一定可以的得到全局最优解。

而如果有负权边的话，无法确定dist[3] + w 和dist[2]到底哪个小，就不能每次贪心地走局部最优的点，贪心失效，Dijkstra算法也就失效了。

算法过程

Bellman - ford 的原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在 n-1 次松弛后还能更新，则说明图中有负环，因此无法得出结果。

(通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新（相当于存在一条经过大于n 个点的最短路，但这张图只有n个点)）

例题

853. 有边数限制的最短路

由于要每次迭代都要遍历一遍所有的边，所以适合用结构体存边

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 10010;
int n, m, k;
int dist[N]; // dist数组
int last[N]; // 用来临时存上次迭代后的dist数组struct Edge{int a, b, w; // 结构体存边
} edges[N];void bellman_ford(){memset(dist, 0x3f, sizeof dist); // 一开始，还没开始迭代，所有点都没确定到源点的最短距离，dist都初始化成正无穷dist[1] = 0; // 源点到源点的最短距离为0for(int i = 0; i < k; i++){ // 迭代k次后的dist[i]就是源点到i的最多经过k条边的最短路memcpy(last, dist, sizeof dist); // 将dist复制一遍，防止前面被松弛的dist后面再去松弛其他点for(int j = 0; j < m; j++){ // 每次遍历所有m条边，用上次迭代的结果进行松弛auto e = edges[j];dist[e.b] = min(dist[e.b], last[e.a] + e.w); // 松弛操作}}
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m >> k;for(int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;edges[i] = {a, b, c}; // 存边}bellman_ford();if(dist[n] > 0x3f3f3f3f / 2) cout << "impossible";else cout << dist[n];return 0;
}

注意：

1. 在每次迭代只前要把当前的dist数组复制一份，由于是每个点同时向外出发，后遍历的点的dist有可能被先遍历的点松弛更新，如果这个时候再用改变后的dist去更新其他点，就会多走一条边，对于限制边数的最短路的问题就会出错。
2. 最后判断点n不可达的条件一定要写dist[n] > 0x3f3f3f3f / 2，而不是dist[n] == 0x3f3f3f3f，因为0x3f3f3f3f是一个确定的值，而非真正的无穷大，这个值在迭代的过程中也可能会受其他点影响而减小，所以判断只需dist[n]大于某个与0x3f3f3f3f相同数量级的数即可

spfa

spfa其实就是bellman_ford算法的升级版本

时间复杂度

最好情况$O(m)$,最坏情况$O(nm)$，一般情况下和堆优化Dijkstra相当，但如果出题人想卡spfa，就会退化成$O(nm)$的bellman_ford算法

算法过程

Bellman-ford算法中，循环n次，每次遍历m条边，每次遍历的时候，把每条边终点的距离更新成最小。
然而，这样就循环遍历了很多用不到的边。比如第一次遍历，只有第一个点的临边是有效的。
事实上，我们只用遍历那些到源点距离变小的点所连接的边即可。

只有当一个点的前驱结点更新了，该节点才会得到更新； 因此考虑到这一点，我们将创建一个队列，每一次加入距离被更新的结点，每次用队列中的节点松弛其临点，再将被松弛的点放到队列里，最后队列为空的时候说明已经没有点可被松弛，也就确定好了所有点到源点的最短路。

同bellman_ford算法一样，spfa也可以判环，用一个cnt数组记录一下当前点被松弛了多少次，每被松弛一次就会经过一个点，如果cnt[i] >= 图的点数-1，那就说明有负环。

如过题中问有没有正环，就改成求spfa求最长路即可

例题

spfa求最短路

spfa求最短路

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;int n, m;
vector<PII> g[N]; // 邻接表存图
int dist[N]; // dist[i]存当前i到源点的最短路
bool st[N]; // 判断当前点在不在队列中，st[i] = true说明在队列中，st[i] = false说明不在队列中int spfa(){memset(dist, 0x3f, sizeof dist); // 一开始，还没开始迭代，所有点都没确定到源点的最短距离，dist都初始化成正无穷dist[1] = 0; // 源点到源点的最短距离为0queue<int> q;q.push(1); // 将源点如对，去松弛它的临点st[1] = true; // 1在队列中while(!q.empty()){int t = q.front();q.pop();st[t] = false; // t出队了for(auto i : g[t]){ // 遍历t的所有出边int ver = i.first, w = i.second; // ver是t的临点，w是边权if(dist[ver] > dist[t] + w){ // 松弛dist[ver] = dist[t] + w;if(!st[ver]){ // 如果被松弛的点不在队列里，就给它入队q.push(ver);st[ver] = true; // 在队列里了}}}}return dist[n];
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;while(m--){int a, b, c;cin >> a >> b >> c;g[a].push_back({b, c}); // a->b 权值为c的边}int t = spfa();if(t == 0x3f3f3f3f) cout << "impossible" << endl;else cout << t << endl;return 0;
}

spfa判环

spfa判断负环

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <functional>
#define endl '\n'
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10;int n, m;
vector<PII> g[N]; // 邻接表存图
int dist[N]; // dist[i]存当前i到源点的最短路
int cnt[N]; // cnt[i]表示当前i点被松弛了多少次（dist[i]是经过多少条边的最短路）
bool st[N]; // 判断当前点在不在队列中，st[i] = true说明在队列中，st[i] = false说明不在队列中bool spfa(){memset(dist, 0x3f, sizeof dist); // 一开始，还没开始迭代，所有点都没确定到源点的最短距离，dist都初始化成正无穷dist[1] = 0; // 源点到源点的最短距离为0queue<int> q;for(int i = 1; i <= n; i++){ // 因为负环不一定经过哪几个点，所以一开始要把所有点都入队q.push(i);st[i] = true; // i在队列中}while(!q.empty()){int t = q.front();q.pop();st[t] = false; // t出队了for(auto i : g[t]){ // 遍历t的所有出边int ver = i.first, w = i.second; // ver是t的临点，w是边权if(dist[ver] > dist[t] + w){ // 松弛dist[ver] = dist[t] + w; // 如果被松弛的点不在队列里，就给它入队cnt[ver] = cnt[t] + 1; // 被松弛的次数+1if(cnt[ver] >= n) return true; // 如果他被松弛了超过n-1次，就一定有负环if(!st[ver]){q.push(ver); st[ver] = true; // ver入队}}}}return false;
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;while(m--){int a, b, c;cin >> a >> b >> c;g[a].push_back({b, c}); // a->b权值为c的边}if(spfa()) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

注意:spfa求负环一开始一定要将所有点都入队，因为负环不一定经过源点，如果你只给源点入队，这图还恰巧不连通，负环还在另一个联通块，就判断错了

Floyd

时间复杂度

$O(n^3)$，效率低，基本点数到500就很极限了，但其他的算法大多只能处理单源最短路，floyd算法可以处理全源最短路（求任意两点之间的最短距离）。

算法原理

floyd算法是基于动态规划的思想，$dp[i][j][k]$表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离

状态转移方程：$dp[i,j,k]=min(dp[i,j,k-1],dp[i,k,k-1]+dp[k,j,k-1]$

优化掉第三维之后，就变成了floyd算法：$d[i][j]=min(d[i][j],d[i][k]+d[k][j])$

简单地说：d[i][j]就是从i到j不经过k的最短路，d[i][k] + d[k][j]就是从i到j经过k的最短路，遍历所有i，j，再遍历所有中间节点k，不断松弛，最后所有的d[i][j]就都是从i到j的最短路了。

例题

Floyd求最短路

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 205;
int n, m, k;
int d[N][N];void floyd(){for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){d[i][j] = min(d[i][j], d[i][k] + d[k][j]); // 状态转移（松弛操作）}}}
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m >> k;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(i == j)d[i][j] = 0; // 自己到自己的距离为0elsed[i][j] = 0x3f3f3f3f; // 其他初始化成正无穷}}while(m--){int a, b, c;cin >> a >> b >> c;d[a][b] = min(d[a][b], c); // 要求最短路，有重边就只要最短的一条}floyd();while(k--){int a, b;cin >> a >> b;int t = d[a][b]; // floyd跑完后，d[a][b]就变成了从a到b的最短路if(t > 0x3f3f3f3f / 2)cout << "impossible" << endl;elsecout << t << endl;}return 0;
}

注意:循环位置不能改，一定要先遍历k，具体为什么，如果会动态规划（dp）的话，再好好想想。

什么时候用哪个最短路算法？

借用一下闫学灿的图

一句话就是：求多源最短路就用floyd，求单源最短路，如果没有负权边就用dijkstra，有负权边就用spfa

如果你记不住那么多最短路算法，堆优化Dijkstra、spfa、floyd，这仨一定要会。

一些特殊题型

次短路

如果一道题要求次短路的话，其实只需要在原来用dist数组记录最短路的基础上，再加一个dist1数组记录到每个点的次短路，在求最短路算法的基础上，在更新时像下面这样写就可以了。

if(dist[j] > dist[t] + w){ // 找到了更短的最短路dist1[j] = dist[j]; // 原来的最短路就变成次短路dist[j] = dist[t] + w; // 更新最短路
}
else if(dist1[j] > dist1[t] + w){ // 如果不比最短路小但是比次短路小dist1[j] = dist1[t] + w; // 就更新次短路
}

简单点解释，就是：如果当前的距离比最短路小，就更新最短路，此时原来的最短路就变成了次短路。如果不比最短路小，就再看当前距离是不是比次短路小，如果比次短路小就更新次短路。

比如用堆优化的dijkstra算法在求最短路的同时求次短路，就可以这样写

int dijkstra(){memset(dist, 0x3f, sizeof dist);memset(dist1, 0x3f, sizeof dist1);dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> q;q.push({0, 1});while(!q.empty()){auto t = q.top();q.pop();int ver = t.second, dis = t.first;if(dis > dist1[ver]) continue;for(auto i : g[ver]){int new_dist = dis + i.second;if(dist[i.first] > new_dist){dist1[i.first] = dist[i.first];dist[i.first] = new_dist;q.push({dist[i.first], i.first});}else if(dist[i.first] < new_dist && dist1[i.first] > new_dist){dist1[i.first] = new_dist;q.push({dist1[i.first], i.first});}}}return dist1[n];
}

例题

P2865 [USACO06NOV] Roadblocks G
Two Paths

最短路计数

和求次短路思路和代码大致相同

int cnt[N]; // cnt 数组用于记录从起点到达某个顶点的不同最短路径的条数。if(dist[j] > dist[t] + w){cnt[j] = cnt[t];dist[j] = dist[t] + w;
}
else if(dist[j] == dist[t] + w){ cnt[j] += cnt[t]; 
}

例题

P1144 最短路计数

分层图

有些求最短路的题目在每个端点都有边权的基础上，还有几次“白嫖”的能力，比如一共有n个点，m条路，走每一条路都要交一定的过路费，同时你还有k次不交过路费的能力，问你从1~n最少要花多少钱，这个时候普通的建边方式就难以解决，就要用到分层图。

分层图的思想

每层有n个点，点a + i * n就是第i层中的a点（从第0层到第k层）。

在建边的时候，层内的点正常连边，不同层之间的点，想实现“不交钱”，你就可以对于每条边，在该层的起点和下一层的终点之间连一条长度为0的边。

// 有向图
cin >> a >> b;
add(a, b, c); 
for(int i = 0; i < k; i++){add(a + i * n, b + (i + 1) * n, 0); // 连相邻两层之间的边add(a + (i + 1) * n, b + (i + 1) * n, c); // 连同层内的边}

// 无向图
cin >> a >> b;
add(a, b, c), add(b, a, c); 
for(int i = 0; i < k; i++){add(a + i * n, b + (i + 1) * n, 0), add(b + i * n, a + (i + 1) * n, 0); // 连相邻两层之间的边add(a + (i + 1) * n, b + (i + 1) * n, c), add(b + (i + 1) * n, a + (i + 1) * n, c); // 连同层内的边}

这样每向下跑一层，就相当于免了一次过路费，最多免k次过路费，就只需要建k层图即可

最后，再给每相邻两层的终点向下连上长度为0的边（因为免过路费的次数可能为0~k次，所以到任意一层的终点都可以，所以要循环一遍，取每个终点的dist的最小值，但为了方便统计，直接用这种方式，就只需要求起点到最后一层的终点的最短路就可以了）

例题

P4568 [JLOI2011] 飞行路线
P2939 [USACO09FEB] Revamping Trails G
P4822 [BJWC2012] 冻结

二分图

什么是二分图

如果一个图中的所有点可以划分成两个点集，使得同一点集中任意两点之间没有边相连，这个图就叫二分图

说人话就是：图中点通过移动能分成左右两部分，左侧的点只和右侧的点相连，右侧的点只和左侧的点相连。

就像下面这样

结论

一个图是二分图 $\iff$这个图中没有奇数环

证明也非常简单，对于下面这个环，尝试将所有点都分到左右两边，如果他是奇数环，通过推一圈下来,第一个点一定是冲突的，所以一定不是二分图

染色法判定二分图

算法原理

想知道一个图是不是二分图，只需给每条边的两个端点染上不同的两种颜色，如果出现了染色冲突的情况，就说明此图不是二分图。

1. 一开始对任意一未染色的顶点染色。
2. 判断其相邻的顶点是否已经染色，若未染色则将其染上和相邻顶点不同的颜色。
3. 若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断。

例题

染色法判定二分图

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 1e5 + 10;int n, m;
int color[N]; // 存当前顶点的颜色，0表示还没染色，1表示已经染了第一种颜色，2表示已经染了第二种颜色
vector<int> g[N]; // 邻接表存图bool dfs(int x, int c){ // 给点i染第c种颜色color[x] = c; // 染色for(int i : g[x]){ // 遍历x的临点if(!color[i]){ // 如果x的临点没染色，就尝试染成另一种颜色if(!dfs(i, 3 - c)) return false; // 染不了就不是二分图}else if(color[i] == c) return false; // 如果临点已经和x染了同一种颜色，染色冲突，不是二分图}return true; // 没有冲突就是二分图
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n >> m;while(m--){int a, b;cin >> a >> b;g[a].push_back(b), g[b].push_back(a); // 无向边}for(int i = 1; i <= n; i++){ // 遍历所有点，给没染色的点染色if(!color[i]){if(!dfs(i, 1)){cout << "No" << endl;return 0;}}}cout << "Yes" << endl;return 0;
}

二分图最大匹配：匈牙利算法

此算法如果买acwing的算法基础课了强烈建议听闫总讲一遍，非常有趣~
传送门

什么是二分图匹配

二分图的匹配：给定一个二分图 $G$，在 $G$ 的一个子图 $M$ 中，$M$ 的边集 { E } \{E\} {E} 中的任意两条边都不依附于同一个顶点，则称 $M$ 是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

举个例子：每个男生都有几个喜欢的女生，此时由每个男女生作为节点，由喜欢的关系作为边，组成的图就是一个二分图，这个时候，现在你是月老，来给他们牵线，你最多能凑成多少对，这个对数就是二分图最大匹配数。

一个拓展结论：二分图最大匹配数 = 最小点覆盖 = 总点数 - 最大独立集 = 总点数 - 最小路径覆盖（因为是图论入门，具体概念不在此赘述）

算法原理

借用闫学灿的解释方法（因为比较通俗易懂并且比较有趣）

void 男找心仪的女() 
{if (女单身) 2人在一起else if (男友有备胎) 就绿了男友else 男继续单身
}

如果你想找的妹子已经有了男朋友，
你就去问问她男朋友，
你有没有备胎，
把这个让给我好吧

例题

861. 二分图的最大匹配

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define endl '\n'
using namespace std;
const int N = 505;int n1, n2, m; //已知二分图，左侧点数为n1，右侧点数为n2
bool st[N]; // 存某个女生被没被考虑过
int match[N]; //记录已有配对情况（match[i]表示当前和i这个女生配对的男生） 
vector<int> g[N]; // 邻接表存边
int res; bool dfs(int x){ // 找xfor(int i : g[x]){ // 遍历x所有喜欢的女生if(!st[i]){ // 如果这个女生没考虑过st[i] = true; // 考虑一下if(!match[i] || dfs(match[i])){ // 她没男朋友，或她现在的男朋友可以换一个女朋友match[i] = x; // 他就和这个女生配对return true; // 这个男生能找到女朋友}}}return false; // 找不到
}int main(){ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n1 >> n2 >> m;while(m--){int a, b;cin >> a >> b;g[a].push_back(b);}for(int i = 1; i <= n1; i++){memset(st, false, sizeof st);if(dfs(i)){ // 如果一个男生能找到女朋友res++; // 对数（匹配数） + 1}}cout << res << endl;return 0;
}

为什么后来者居上，因为前者他不争不抢啊~