钱力古的小博客

最短路

dijkstra

模板

c++

// 朴素版
int dijkstra() {
  memset(dist, 0x3f, sizeof dist);  // 初始化所有距离为无穷

  dist[1] = 0;                   // 开始点距离为0
  for (int i = 0; i < n; i++) {  // 走图
    int t = -1;  // 找到当前未确定最短距离的点中 距离最小的点

    for (int j = 1; j <= n; j++)
      if (!st[j] &&
          (t == -1 ||
           dist[t] > dist[j]))  //如果没有标记过 而且是第一个点或者距离偏小
        t = j;                  // 找到这个点

    st[t] = true;                 // 走距离最小的那个点
    for (int j = 1; j <= n; j++)  // 给所有值全部赋最短的(更新)
      dist[j] = min(dist[j], dist[t] + g[t][j]);  // 取最短的
  }
  //	cout<<0x3f3f3f3f<<endl;
  if (dist[n] == 0x3f3f3f3f) return -1;  // 不连通
  return dist[n];                        // 返回最小距离
}

// 堆优化
int dijkstra() {
  memset(dist, 0x3f, sizeof(dist));
  dist[1] = 0;
  priority_queue<PII, vector<PII>, greater<PII>> heap;  // 定义一个小根堆

  heap.push({0, 1});
  // 这个顺序不能倒，pair排序时是先根据first，再根据second，这里显然要根据距离排序
  while (heap.size()) {
    PII k = heap.top();  // 取不在集合S中距离最短的点
    heap.pop();
    int ver = k.second, distance = k.first;

    if (st[ver]) continue;
    st[ver] = true;  // 被标记过 说明当前点是冗余的

    for (int i = h[ver]; i != -1; i = ne[i]) {
      int j = e[i];  // i只是个下标 e中在存的是i这个下标对应的点
      if (dist[j] > distance + w[i]) {
        dist[j] = distance + w[i];  // 更新距离
        heap.push({dist[j], j});
      }
    }
  }
  if (dist[n] == 0x3f3f3f3f)
    return -1;
  else
    return dist[n];
}

模板应用起来很容易，看一些变形

二元组最短路

LCP 35. 电动车游城市
求解 start->end 的最短路（最短时间），但约束条件是
电动车行驶容量上限为 cnt
每个点都有一个 chrage[i]，表示充一格电的时间
数据范围：n<200, cnt<100, charge[i]<100
可能有重边！

容易想到设计 (u, power) 作为状态的表示，但在这种表示下如何求解最短路？

正确的抽象：进行一个映射，即有 n*cnt 个点，求解的终点就是 (end, 0) 对应的值

怎么更新最短路？分成两部分

(u, power) 不充电的情况下可以更新的距离：考虑邻居和边权
充电的话只充一格电，即 (u, power)->(u,power+1)，接下来的事情交给这个点的逻辑去处理

c++

class Solution {
public:
    using PII = pair<int, int>;
    int electricCarPlan(vector<vector<int>>& paths, int cnt, int start, int end, vector<int>& charge) {
        int n = paths.size();
        int g[n][n];
        memset(g, 0x3f, sizeof g);
        for (auto &t: paths) 
            g[t[0]][t[1]] = g[t[1]][t[0]] = min(g[t[0]][t[1]], t[2]);
        
        auto encode = [&](int u, int p) -> int {
            return u * (cnt + 1) + p;
        };

        auto decode = [&](int mask) -> PII {
            return {mask / (cnt + 1), mask % (cnt + 1)};
        };

        int dist[n * (cnt + 1)];
        bool st[n * (cnt + 1)];
        memset(dist, 0x3f, sizeof dist);
        memset(st, 0, sizeof st);
        priority_queue<PII, vector<PII>, greater<PII>> q;

        dist[encode(start, 0)] = 0;
        q.push({0, encode(start, 0)});
        while (q.size()) {
            auto [d, mask] = q.top();
            q.pop();
            if (st[mask]) continue;
            st[mask] = 1;
            auto [u, p] = decode(mask);
            if (u == end) return d; // 第一次到达 此时 power=0
            // neighbor
            for (int i = 0; i < n; i++) {
                int len = g[u][i];
                if (len == 0x3f3f3f3f) continue;
                if (p >= len)
                    if (int nxt = encode(i, p - len); d + len < dist[nxt]) {
                        dist[nxt] = d + len;
                        q.push({d + len, nxt});
                    }
            }
            // charge
            if (p < cnt && d + charge[u] < dist[mask + 1]) {
                dist[mask + 1] = d + charge[u];
                q.push({d + charge[u], mask + 1});
            }
        }
        return -1;
    }
};

环相关

拓扑排序

模板，很容易记住了

无向图的话，应该是 --deg[v] == 1 作为判断条件

c++

bool topsort() {
	int hh = 0, tt = -1;
	for (int i = 1; i <= n; i++)
		if (!d[i])
			q[++tt] = i;
	while (hh <= tt) {
		int t = q[hh++];
		for (int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			d[j]--;
			if (d[j] == 0)
				q[++tt] = j;
		}
	}
	return tt == n - 1;
}

内向基环树

每个连通块必定有且仅有一个环，且由于每个点的出度均为 1 ，这样的有向图又叫做内向基环树

每一个内向基环树（连通块）都由一个基环和其余指向基环的树枝组成

处理方法：

我们可以通过一次拓扑排序「剪掉」所有树枝，因为拓扑排序后，树枝节点的入度均为 0 ，基环节点的入度均为 1
- 如果要遍历基环，可以从拓扑排序后入度为 1 的节点出发，在图上搜索
- 如果要遍历树枝，可以以基环与树枝的连接处为起点，顺着反图来搜索树枝（搜索入度为 0 的节点），从而将问题转化成一个树形问题
创建反图的过程可以在拓扑排序中完成，这样创建的反图是不包含基环的

模板：2127. 参加会议的最多员工数

cpp

        vector<int> deg(n);
        for (int f: favorite) {
            deg[f]++; // 统计基环树每个节点的入度
        }

        vector<vector<int>> rg(n); // 反图
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (deg[i] == 0) {
                q.push(i);
            }
        }
        while (!q.empty()) { // 拓扑排序，剪掉图上所有树枝
            int x = q.front();
            q.pop();
            int y = favorite[x]; // x 只有一条出边
            rg[y].push_back(x);
            if (--deg[y] == 0) {
                q.push(y);
            }
        }

另一种做法

cpp

class Solution {
public:
    int maximumInvitations(vector<int>& favorite) {
        // case 1
        // 可能存在一个长度为 2 的环 即两个人互相喜欢 那么这两个节点可以各自扩展出一条追随者链
        // 这两个节点安排到一起 各自的追随者链往两边扩散
        // 若存在多种 case 1 都可以安排上
        // case 2
        // 存在长度为 2 以上的环时 就把这个环的所有节点安排坐在一起
        // 若存在多种 case 2 只能安排一种
        // 答案即为 两种 case 的较大者

        // 拓扑 + dfs 找长度
        int n = favorite.size();
        vector<int> d(n); // 统计入度
        for (int i = 0; i < n; i++)
            d[favorite[i]]++;
        // 拓扑排序 排除不在环里的节点
        vector<int> follower(n); // 追随者链的长度
        vector<bool> vis(n, false);
        vector<int> q(n);
        int hh = 0, tt = -1;
        for (int i = 0; i < n; i++)
            if (!d[i]) q[++tt] = i;
        while (hh <= tt) {
            int t = q[hh++];
            vis[t] = true;
            int u = favorite[t];
            follower[u] = max(follower[u], follower[t] + 1);
            if (--d[u] == 0) 
                q[++tt] = u; 
        }
        // 找长度
        int two = 0, res = 0;
        for (int i = 0; i < n; i++) {
            if (vis[i]) continue; // 在追随者链中 跳过
            for (int u = i, len = 0; ; len++, u = favorite[u]) { // dfs
                if (!vis[u]) vis[u] = true; // 还在环内
                else { // 有向环遍历完成
                    //累计计算节点个数为2的有向环的答案，需加上各自最长追随者链的个数
                    if (len == 2) two += 2 + follower[i] + follower[favorite[i]];  
                    else res = max(res, len); // 更新 case 2 的答案
                    break;
                }
            }
        }
        return max(res, two);
    }   
};

基环树模板题：ABC266F

给定个点条边，每次询问回答和之间的简单路径是否唯一

cpp

        vector<vector<int>> g(n + 1);
        vector<int> deg(n + 1);
        for (int i = 0, u, v; i < n; i++) {
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
            deg[u] ++;
            deg[v] ++;
        }
        queue<int> q;
        for (int i = 1; i <= n; i++) {
            if (deg[i] == 1) {
                q.push(i);
            }
        }
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int v: g[u]) {
                if (-- deg[v] == 1) {
                    q.push(v);
                }
            }
        }
        vector<int> ids(n + 1);
        int id = 0;
        auto dfs = [&](auto &&dfs, int u, int fa) -> void {
            ids[u] = id;
            for (int v: g[u]) {
                if (v != fa && deg[v] < 2) {
                    dfs(dfs, v, u);
                }
            }
        };
        for (int i = 1; i <= n; i++) {
            if (deg[i] > 1) {
                id ++;
                dfs(dfs, i, 0);
            }
        }
        cin >> m;
        while (m -- ) {
            int u, v;
            cin >> u >> v;
            if (ids[u] == ids[v]) {
                cout << "Yes" << '\n';
            } else {
                cout << "No" << '\n';
            }
        }

无向图环相关

无向图判断有无环的话，可以 dfs 然后用 V == E/2+1 来判断

如果想知道哪些点在环上怎么办？

LCP 21. 追逐游戏
有 n 个点，n 条边构成无向连通图。A 要追 B，开始时在不同位置上，每秒钟 A 先行动，B 在行动
行动分为两种：不动，移动至邻点
问最少需要几秒追到，或追不到
数据范围 1e5

这道题自己想出了一部分，首先从样例可以得到提示，如果有一个环，那么就抓不到，否则的话，B 应该要逃到某个叶子节点上。那么首先要用 bfs 求最短路，知道 A 到每个点的最短距离，然后求 B 的最短路，也是 bfs，只是如果一个点 B 的最短距离大于 A 的话，就认为这个点不可达，因为不能途径这个点逃到别的点上去

然后就要考虑哪些点在环上了，这部分没想到

本题只有 n 条边，因此最多只有一个环！
B 如果先逃到环上，那么就抓不到
如果环长只有 3，就算先逃到环上，也一定会被抓住
怎么判环：类似于拓扑排序，记录每个点的出度，初始时把出度为 1 的点入队，最后出度为 2 的点就在环上

c++

// 找环 拓扑排序 找环
queue<int> q;
for(int i = 1;i <= n;i ++) if(isRing[i] == 1) q.push(i);
while(!q.empty()) {
    int t = q.front(); q.pop();
    for(auto& next : g[t]) {
        if(isRing[next] == 1) continue;
        isRing[next] --;
        if(isRing[next] == 1) q.push(next);
    }
}

不被抓到的条件：B 在大于 3 的环上，或者 B 可以先逃到环上
否则，遍历每个点求最长时间差

c++

class Solution {
public:
    const int INF = 0x3f3f3f3f;
    int chaseGame(vector<vector<int>>& edges, int startA, int startB) {
        int n = edges.size();
        vector<int> g[n + 1];
        vector<int> d(n + 1);
        for (auto &e: edges) {
            g[e[0]].push_back(e[1]);
            g[e[1]].push_back(e[0]);
            d[e[0]] ++, d[e[1]] ++;
            // 特判
            if (e[0] == startA && e[1] == startB) return 1;
            if (e[1] == startA && e[0] == startB) return 1;
        }
        vector<int> distA(n + 1, INF);
        vector<bool> st(n + 1);
        int cnt = -1;
        queue<int> q;
        q.push(startA);
        st[startA] = 1;
        while (q.size()) {
            ++ cnt;
            int sz = q.size();
            while (sz -- ) {
                int x = q.front();
                q.pop();
                distA[x] = cnt;
                for (int y: g[x])
                    if (!st[y]) {
                        st[y] = 1;
                        q.push(y);
                    }
            }
        }
        vector<int> distB(n + 1, INF);
        fill(st.begin(), st.end(), 0);
        cnt = -1;
        q.push(startB);
        st[startB] = 1;
        while (q.size()) {
            ++ cnt;
            int sz = q.size();
            while (sz -- ) {
                int x = q.front();
                q.pop();
                distB[x] = cnt;
                for (int y: g[x])
                    if (!st[y] && cnt + 1 < distA[y]) {
                        st[y] = 1;
                        q.push(y);
                    }
            }
        }
        for (int i = 1; i <= n; i++)
            if (d[i] == 1) q.push(i);
        while (q.size()) {
            int x = q.front();
            q.pop();
            // d[x] --;
            for (int y: g[x]) {
                if (d[y] == 1) continue;
                if (-- d[y] == 1) q.push(y);
            }
        }
        int ring = 0;
        for (int i = 1; i <= n; i++)
            if (d[i] == 2) ring ++;
        
        if (ring > 3) {
            if (d[startB] == 2) return -1;
            for (int i = 1; i <= n; i++)
                if (d[i] == 2 && distB[i] < distA[i] - 1) return -1;
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            // cout << i << ' ' << distA[i] << ' ' << distB[i] << endl;
            if (distB[i] < distA[i] - 1) {
                res = max(res, distA[i]);
            }            
        }

        return res;
    }
};

二分图相关

一道典题

2493. 将节点分成尽可能多的组
给一个无向图，不一定连通，把顶点分组，满足每个点都属于一个组，对于边 (a, b)，abs(group[a]-group[b])=1，问最多分成几个组
点数<500，边数是 1e4

每条边的两个顶点不属于同一个组，有点二分图的意思，又有点按层分组的意味，是不是要 bfs？

规定第 1 组里只有一个点，枚举这个点 s 并对整个连通块进行 BFS。设点 s 到同一连通块内点 u 的最短距离为 d(u)，那么点 u 就被分在第 d(u)+1 组。我们枚举连通块中的所有边 (u,v) 并检查是否合法，如果解合法，那么答案就是 max(d(u))+1

接下来证明这个做法的最优性。

首先说明如果该做法无法求出解，则原图一定无解。

根据最短路的三角不等式，任意一条边 (u,v) 都满足 ∣d(u)−d(v)∣≤1。也就是说，当且仅当同一组内的两个点有连边时，该做法无法求出解。而如果同一组内的两个点有连边，则说明原图有奇环，一定无解。

无奇环等价于二分图，也可以先用染色法判断二分图

接下来说明存在一个最优解，使得第 1 组一定只有一个点。

假设最优解中第 1 组有超过一个点，那么这些点肯定与第 2 组中的点有连边。因此我们可以把多余的点都移动到第 3 组，解仍然可行，且不会变差

c++

class Solution {
public:
    int magnificentSets(int n, vector<vector<int>>& edges) {
        vector<int> e[n + 1];
        for (auto &edge : edges) {
            e[edge[0]].push_back(edge[1]);
            e[edge[1]].push_back(edge[0]);
        }

        // mp[i] 表示 i 代表的连通块的答案
        unordered_map<int, int> mp;

        // 以 S 作为 BFS 的起点
        // 以连通块中编号最小的点 mn 为代表
        // 把这个连通块的解记到 mp[mn] 里
        auto bfs = [&](int S) {
            int mn = S;
            queue<int> q;
            int dis[n + 1];
            memset(dis, 0, sizeof(dis));
            q.push(S); dis[S] = 1;
            while (!q.empty()) {
                int sn = q.front(); q.pop();
                mn = min(mn, sn);
                for (int fn : e[sn]) {
                    if (dis[fn]) continue;
                    q.push(fn);
                    dis[fn] = dis[sn] + 1;
                }
            }

            int &ret = mp[mn];
            // 检查分组的合法性
            for (int i = 1; i <= n; i++) if (dis[i]) for (int fn : e[i]) if (abs(dis[i] - dis[fn]) != 1) return;
            // 求最大距离
            for (int i = 1; i <= n; i++) if (dis[i]) ret = max(ret, dis[i]);
        };

        // 枚举以每个点作为 BFS 的起点，并更新所属连通块的答案
        for (int i = 1; i <= n; i++) bfs(i);

        int ans = 0;
        // 枚举所有连通块
        for (auto it = mp.begin(); it != mp.end(); it++) {
            // 只要有一个连通块无解就无解
            if (it->second == 0) return -1;
            // 否则答案就是所有连通块的解的总和
            ans += it->second;
        }
        return ans;
    }
};

其它板子

二分图染色法判断

cpp

// 二分图当且仅当图中不存在奇数环

/*
860. 染色法判定二分图

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。
*/

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 100010, M = 200010;

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]) {
      // 把 1 变成 2 把 2 变成 1 的技巧
      if (!dfs(j, 3 - c)) return false;
    } else if (color[j] == c)
      return false;
  }

  return true;
}

int main() {
  scanf("%d%d", &n, &m);

  memset(h, -1, sizeof h);

  while (m--) {
    int a, b;
    scanf("%d%d", &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;
}

堆优化 prim

cpp

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int>PII;
const int N = 2e3 + 10;
int e[N], ne[N], idx, h[N], w[N];
int n, m, val;
int dist[N];
bool st[N];
int g[N][N];

void add(int a, int b, int c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

int Prim() {
	memset(vis, false, sizeof vis);
	int sum = 0, cnt = 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, dst = t.first;
		if (vis[ver])
			continue;
		vis[ver] = true, sum += dst, ++cnt;

		for (int i = h[ver]; i != -1; i = ne[i]) {
			int j = e[i];
			if (!vis[j]) {
				q.push({w[i], j});
			}
		}
	}

	if (cnt != n)
		return INF;
	return sum;
}

int main() {
	cin >> n >> m;
	memset(h, -1, sizeof h);
	memset(g, 0x3f, sizeof g);
	while (m--) {
		int a, b, c;
		cin >> a >> b >> c;
//		add(a, b, c), add(b, a, c);
		g[a][b] = min(g[a][b], c);
	}
	prim();
//	for (int i = 1; i <= n; i++)
//		val = max(val, dist[i]);
	cout << n - 1 << " " << val << endl;
	return 0;
}

拓展 dfs 求割点

cpp

#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 100010, M = 2000010;
int h[N], e[M], ne[M], idx;
int n, m, cnt, t;
int d[N], low[N], p[N], children[N];
bool st[N], res[N];

int pa[N];
int find(int x) {
  if (pa[x] != x) pa[x] = find(pa[x]);
  return pa[x];
}

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

void dfs(int u) {
  t++;
  d[u] = t;
  low[u] = d[u];
  st[u] = true;

  for (int i = h[u]; ~i; i = ne[i]) {
    int j = e[i];
    if (!st[j]) {
      p[j] = u;
      children[u]++;
      dfs(j);
      low[u] = min(low[u], low[j]);
      if (p[u] == 0 && children[u] >= 2)
        res[u] = true;
      else if (p[u] != 0 && low[j] >= d[u])
        res[u] = true;
    } else if (j != p[u])
      low[u] = min(low[u], d[j]);
  }
}

int main() {
  scanf("%d%d", &n, &m);
  memset(h, -1, sizeof h);
  for (int i = 1; i <= n; i++) pa[i] = i;

  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    if (a != b) {
      add(a, b);
      add(b, a);
    }
    if (find(a) != find(b)) pa[a] = b;
  }

  for (int i = 1; i <= n; i++)
    if (pa[i] == i) {
      t = 0;
      if (!st[i]) dfs(i);
    }

  for (int i = 1; i <= n; i++)
    if (res[i]) cnt++;
  printf("%d\n", cnt);
  for (int i = 1; i <= n; i++)
    if (res[i]) printf("%d\n", i);

  return 0;
}

欧拉回路与欧拉路径

cpp

/*
对无向图
（1）存在欧拉路径的充要条件：度数为奇数的点只能有0个或2个
（2）存在欧拉回路的充要条件：度数为奇数的点只能有0个
对有向图
（1）存在欧拉路径的充要条件：要么所有点入度等于出度，要么只有两个点不是（起点、终点）
（2）存在欧拉回路的充要条件：所有点入度等于出度
*/

// Acwing 1186 欧拉路径
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100010, M = 400010;

int h[N], e[M], ne[M], idx;
int type, n, m, din[N], dout[N], cnt, res[M];
bool st[M];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int u)
{
    for (int& i = h[u]; i != -1; ) // 通过引用来达到修改 h[u] 的目的
    {
        if (st[i])
        {
            i = ne[i];
            continue;
        }
        
        if (type == 1) st[i ^ 1] = 1;

/*
对于无向图其在读入的时候的边为 x , 链式前向星中的边的编号为 (x - 1) * 2 , (x - 1) * 2 + 1

对于有向图其在读入的时候的边为 x , 链式前向星中的边的编号为 (x - 1) 
*/

        int t; // 获取边
        if (type == 1)
        {
            t = i / 2 + 1;
            if (i & 1) t = -t;
        }
        else t = i + 1;
        
        int j = e[i];
        i = ne[i]; // 更新当前边
        dfs(j);
        
        res[++ cnt] = t;
    }
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d%d", &type, &n, &m);
    
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        if (type == 1) add(b, a); // 无向图
        din[b] ++, dout[a] ++;
    }
    
    if (type == 1)
        for (int i = 1; i <= n; i++)
            if (d[in] + dout[i] & 1)
            {
                puts("NO");
                return 0;
            }
    else
        for (int i = 1; i <= n; i++)
            if (din[i] != dout[i])
            {
                puts("NO");
                return 0;
            }
    
    for (int i = 1; i <= n; i++)
        if (h[i] != -1)
        {
            dfs(i);
            break;
        }
    
    if (cnt < m)
    {
        puts("NO");
        return 0;
    }
    
    puts("YES");
    for (int i = cnt; i; i--) printf("%d ", res[i]);
    
    return 0;
}

双向 dfs

cpp

// https://www.acwing.com/problem/content/173/

#include <algorithm>
#include <iostream>
#include <vector>


using namespace std;

typedef long long LL;

const int N = 1 << 24;

int n, m, k;
int g[50], weights[N];
int cnt = 0;
int ans;

void dfs(int u, int s) {
  if (u == k) {
    weights[cnt++] = s;
    return;
  }

  if ((LL)s + g[u] <= m) dfs(u + 1, s + g[u]);
  dfs(u + 1, s);
}

void dfs2(int u, int s) {
  if (u == n) {
    int l = 0, r = cnt - 1;
    while (l < r) {
      int mid = l + r + 1 >> 1;
      if (weights[mid] + (LL)s <= m)
        l = mid;
      else
        r = mid - 1;
    }
    if (weights[l] + (LL)s <= m) ans = max(ans, weights[l] + s);

    return;
  }

  if ((LL)s + g[u] <= m) dfs2(u + 1, s + g[u]);
  dfs2(u + 1, s);
}

int main() {
  cin >> m >> n;
  for (int i = 0; i < n; i++) cin >> g[i];

  sort(g, g + n);
  reverse(g, g + n);

  k = n / 2;  // 防止 n = 1时，出现死循环
  dfs(0, 0);

  sort(weights, weights + cnt);
  int t = 1;
  for (int i = 1; i < cnt; i++)
    if (weights[i] != weights[i - 1]) weights[t++] = weights[i];
  cnt = t;

  dfs2(k, 0);

  cout << ans << endl;

  return 0;
}

匈牙利算法

cpp

/*
861. 二分图的最大匹配

给定一个二分图，其中左半部包含 n1 个点（编号 1∼n1），右半部包含 n2 个点（编号
1∼n2），二分图共包含 m 条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。
*/

#include <cstring>
#include <iostream>

using namespace std;
const int N = 510, M = 100010;
int n1, n2, m;
int h[N], ne[M], e[M], idx;
bool st[N];
int match[N];

void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }

int find(int x) {
  //遍历自己喜欢的女孩
  for (int i = h[x]; i != -1; i = ne[i]) {
    int j = e[i];
    if (!st[j]) {  //如果在这一轮模拟匹配中 这个女孩尚未被预定
      st[j] = true;  //那 x 就预定这个女孩了
      //如果女孩j没有男朋友 或者她原来的男朋友能够预定其它喜欢的女孩 配对成功
      if (!match[j] || find(match[j])) {
        match[j] = x;
        return true;
      }
    }
  }
  //自己中意的全部都被预定了 配对失败
  return false;
}

int main() {
  cin >> n1 >> n2 >> m;
  memset(h, -1, sizeof h);

  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 << endl;
}

bellman-ford

cpp

#include <cstring>
#include <iostream>

/*
853. 有边数限制的最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n
号点，输出 impossible。

注意：图中可能 存在负权回路 。
*/

using namespace std;

const int N = 510, M = 10010;

struct Edge {
  int a;
  int b;
  int w;
} e[M];  // 把每个边保存下来即可
int dist[N];
int backup[N];  // 备份数组防止串联
int n, m, k;    // k代表最短路径最多包含k条边

int bellman_ford() {
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  for (int i = 0; i < k; i++) {         // k次循环
    memcpy(backup, dist, sizeof dist);  // 只用上一次迭代的数据
    for (int j = 0; j < m; j++) {       // 遍历所有边
      int a = e[j].a, b = e[j].b, w = e[j].w;
      dist[b] = min(dist[b], backup[a] + w);
      // 使用 backup: 避免给 a 更新后立马更新 b 这样 b
      // 一次性最短路径就多了两条边出来
    }
  }
  if (dist[n] > 0x3f3f3f3f / 2)
    return -1;  // 路径不存在
  else
    return dist[n];
}

int main() {
  scanf("%d%d%d", &n, &m, &k);
  for (int i = 0; i < m; i++) {
    int a, b, w;
    scanf("%d%d%d", &a, &b, &w);
    e[i] = {a, b, w};
  }
  int res = bellman_ford();
  if (res == -1)
    puts("impossible");
  else
    cout << res;

  return 0;
}

Hierholzer

cpp

/*
给定一张有 500 个顶点的无向图，求这张图的一条欧拉路或欧拉回路。如果有多组解，输出最小的那一组。

在本题中，欧拉路或欧拉回路不需要经过所有顶点。

边的数量 m 满足 1 <= m <= 1024。
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

typedef pair<int, int> PII;
#define x first
#define y second

const int N = 1010;
int n, start, m, top;
int d[N], idx[N], ans[N << 3];
map<PII, int> mp; // (u, v)
vector<int> edge[N];

void Euler(int u)
{
    while (1)
    {
        while (idx[u] < edge[u].size() && !mp[{u, edge[u][idx[u]]}]) 
            idx[u] ++; // 如果反向边走过就不走了
        if (idx[u] >= edge[u].size()) break;
        
        int v = edge[u][idx[u]];
        mp[{u, v}] --;
        mp[{v, u}] --; // 标记反向边
        idx[u] ++;
        
        Euler(v);
    }
    ans[++ top] = u;
}

int main()
{
    scanf("%d", &m); // 输入边的数量
    start = n = 550; // 本题顶点序号最多500
    
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
        d[u] ++, d[v] ++;
        
        start = min(start, min(u, v));
        
        mp[{u, v}] ++, mp[{v, u}] ++;
    }
    
    for (int i = 1; i <= n; i++)
        if (d[i] & 1)
        {
            start = i;
            break; // 寻找序号最小的起点
        }
    
    for (int i = 1; i <= n; i++)
        sort(edge[i].begin(), edge[i].end());
    
    Euler(start);
    
    while (top)
        printf("%d\n", ans[top --]); // 输出路径
    
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

const int N = 1010;

int g[N][N];
int d[N];
stack<int> s; // 储存答案的栈 由于是回溯时存答案 因此需要反向输出
int m, n;
int start = 0x3f3f3f3f;

void Euler(int u)
{
    for (int i = 1; i <= n; i++) // 枚举每个顶点
    {
        if (g[u][i]) // 有边
        {
            g[u][i] --;
            g[i][u] --; // 标记反向边
            
            Euler(i);
        }
    }
    s.push(u);
}

int main()
{
    scanf("%d", &m);
    
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u][v] ++, g[v][u] ++; // 可能有重边
        d[u] ++, d[v] ++;
        
        start = min(start, min(u, v));
    }
    
    n = 500;
    for (int i = 1; i <= n; i++)
        if (d[i] % 2)
        {
            start = i;
            break;
        }
        
    Euler(start);
    
    while (!s.empty())
    {
        printf("%d\n", s.top());
        s.pop();
    }
    
    return 0;
}

kruskal

cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, m, p[N];

struct Edge {
  int a, b, w;
  bool operator<(const Edge &W) const { return w < W.w; }
} edges[N];

/*
适用于稀疏图
将所有边按权重从小到大排序 （时间复杂度瓶颈）
枚举每条边 a b 权重 c
        if a b 不连通
                将这条边加入集合中

算法实现通过并查集
*/

int find(int x) {
  if (x != p[x]) p[x] = find(p[x]);
  return p[x];
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, w;
    cin >> a >> b >> w;
    edges[i] = {a, b, w};
  }
  // Kruskal 实现
  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) {
      res += w;  // 权值加进来
      cnt++;     // 当前边数
      p[a] = b;
    }
  }
  if (cnt != n - 1)
    puts("impossible");
  else
    cout << res << endl;
  return 0;
}

spfa

cpp

// spfa 是对 bellman_ford 的优化
// 只有 a 变小了 b 才会变小
// 不存在负权回路才适用

/*
851. spfa求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出
impossible。

数据保证不存在负权回路。
*/

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int N = 1e5 + 10;

#define fi first
#define se second

typedef pair<int, int> PII;  //到源点的距离，下标号

int h[N], e[N], w[N], ne[N], idx = 0;
int dist[N];  //各点到源点的距离
bool st[N];
int n, m;
void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int spfa() {
  queue<PII> q;
  memset(dist, 0x3f, sizeof dist);
  dist[1] = 0;
  q.push({0, 1});
  st[1] = true;
  while (q.size()) {
    PII p = q.front();
    q.pop();
    int t = p.second;
    st[t] = false;
    //从队列中取出来之后该节点 st 被标记为 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]) {
          //当前已经加入队列的结点 无需再次加入队列
          //即便发生了更新也只用更新数值即可 重复添加降低效率
          st[j] = true;
          q.push({dist[j], j});
        }
      }
    }
  }
  if (dist[n] == 0x3f3f3f3f)
    return -1;
  else
    return dist[n];
}

int main() {
  scanf("%d%d", &n, &m);
  memset(h, -1, sizeof h);
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }
  int res = spfa();
  if (res == -1)
    puts("impossible");
  else
    printf("%d", res);

  return 0;
}

判负权回路

cpp

/*
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你判断图中是否存在负权回路。
*/

// 用 cnt 数组维护从起点到 x 的距离 如果出现 cnt[x] >= n
// 表明路径上有 n + 1 个点 即存在环

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int N = 2010, M = 10010;

int n, m;
int h[N], w[M], e[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];

void add(int a, int b, int c) {
  e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool spfa() {
  queue<int> q;

  for (int i = 1; i <= n; i++) {
    // 所有点都可以是起点 因此全部要入队
    st[i] = true;
    q.push(i);
  }

  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() {
  scanf("%d%d", &n, &m);

  memset(h, -1, sizeof h);

  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    add(a, b, c);
  }

  if (spfa())
    puts("Yes");
  else
    puts("No");

  return 0;
}

最短路 ​

dijkstra ​

二元组最短路 ​

环相关 ​

拓扑排序 ​

内向基环树 ​

无向图环相关 ​

二分图相关 ​

一道典题 ​

其它板子 ​

二分图染色法判断 ​

堆优化 prim ​

拓展 dfs 求割点 ​

欧拉回路与欧拉路径 ​

双向 dfs ​

匈牙利算法 ​

bellman-ford ​

Hierholzer ​

kruskal ​

spfa ​

最短路