算法基础图论

并查集

可以合并，可以查询联通关系的集合。
初始化

1	pre[i] = i;

找根

int root(int x) {
	if (pre[x] == x) return x;
	return root(pre[x]);
}

合并

1
2
3

void merge(int u, int v) {
	pre[root(u)] = root(v);
}

查询u,v是否联通

1
2
3

void query(int u, int v) {
	root(u) == root(v);
}

路径压缩：
经过

找根操作后，直接将每个点的出点指向根。

1
2
3

void root(u) {
	pre[u] = pre[u]==u ? u : root(pre[u]);
}

换根操作：
多出一个节点或一个连通块，可以将这个节点或连通块的根指向原来的连通块根，也可将原来的根指向新增的节点或连通块，前者称为按秩合并(小->大)。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;

int pre[N], cnt[N];

int root(int x) { return pre[x] = (pre[x] == x ? x : root(pre[x])); }

void merge(int x, int y) { pre[root(x)] = root(y); }

bool isCon(int x, int y) { return root(x) == root(y); }

int main() {
  int n, m;
  cin >> n >> m;

  for (int i = 1; i <= n; ++i) {
    pre[i] = i;
  }

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    merge(u, v);
  }
  // 遍历每个点，每个点的根计数+1
  for (int i = 1; i <= n; ++i) {
    cnt[root(i)]++;
  }

  vector<int> v;
  // 存入非零点
  for (int i = 1; i <= n; ++i) {
    if (cnt[i])
      v.push_back(cnt[i]);
  }
  sort(begin(v), end(v));
  for (auto &i : v) {
    cout << i << ' ';
  }
}

Dijkstra单源最短路

单源：可以求任意一个点到某个点的最短路

graph LR
1-->|1|2
1-->|4|3
2-->|2|3
2-->|2|4
3-->|3|5

从1开始，数组d[i]存放1到i点距离的最小值。
初始化d[1]=0,d[i] = inf
1->2: d[2] = 1
1->3: d[3] = 4
2->3: d[3] = min(1+2, 4) = 3
2->4: d[4] = 1 + 2 = 3
3->5: d[5] = 3 + 3 = 6
贪心思想：每次找最近的点进行拓展和更新
dp：选取最优方案
每个点只拓展更新一次

#include <bitset>
#include <iostream>
#include <vector>
#include <array>
using namespace std;
using ll = long long;
const int N = 1e3 + 5;
// O(n^2)
struct Edge {
  int x, w;
};

vector<Edge> g[N];
array<ll, N> d;
ll n, m;

void dijkstra(int st) {
  d.fill(0x3f);
  d[st] = 0;
  bitset<N> vis; // 表示已经拓展过
  for (int i=1;i<=n;++i) {
    // 找出最小点，距离原点最近
    int u = 1;
    for (int j = 1; j <= n; ++j) {
      if (vis[u] || (!vis[j] && d[j] < d[u]))
        u = j;
    }
    vis[u] = 1; // 表示u已经拓展过
    // d[u]已是最优的
    for (auto &[v, w] : g[u]) {
      if (!vis[v] && d[v] > d[u] + w)
        d[v] = d[u] + w;
    }
  }
}

int main() {
  cin >> n >> m;
  for (ll i=1;i<=m;++i) {
    int u, v, w;
    cin >> u >> v >> w;
    if (u !=v) g[u].push_back({v, w});
  }
  dijkstra(1);
  // 判断是否能到达
  cout << (d[n]>= 0x3f3f3f3f3f3f3f3f ? -1 : d[n]) << '\n';
}

最短路单调队列优化

#include <bitset>
#include <iostream>
#include <queue>
#include <vector>
#include <array>
using namespace std;
using ll = long long;
const int N = 1e3 + 5;

struct Edge {
  ll x, w;
  bool operator<(const Edge &v) const {
    // w小的优先
    return w == v.w ? x < v.x: w > v.w;
  }
};

vector<Edge> g[N];
array<ll, N> d;
ll n, m;

void dijkstra(int st) {
  d.fill(0x3f3f3f3f3f3f3f3f);
  d[st] = 0;
  bitset<N> vis; // 表示已经拓展过

  priority_queue<Edge> pq;
  pq.push({st, d[st]});
  while (pq.size()) {
    int x = pq.top().x;pq.pop();

    // 防止反复入队
    if (vis[x])
      continue;
    vis[x] = 1;

    for (auto &[y, w] : g[x]) {
      if (!vis[y] && d[y] > d[x] + w) {
        d[y] = d[x] + w;
        pq.push({y, d[y]});
      }
    }
  }

}

int main() {
  cin >> n >> m;
  for (ll i=1;i<=m;++i) {
    int u, v, w;
    cin >> u >> v >> w;
    if (u !=v) g[u].push_back({v, w});
  }
  dijkstra(1);
  // 判断是否能到达
  cout << (d[n]>= 0x3f3f3f3f3f3f3f3f ? -1 : d[n]) << '\n';
  
}

Floyd多源最短路

graph LR
1-->|1|2
2-->|5|3
1-->|2|4
4-->|3|3

floyd由三重循环组成，第一层枚举中转点，第二层枚举入点，第三层枚举出点。
有以下图，虚线代表路径中有其他节点。

graph LR
i-.->j
i-.->k
k-.-j

那么从i到j的最短距离

1	d[i][j]=min(d[i][j], d[i][k]+d[k][j])

#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 300;
const ll inf = 4e18, p = 998244353;

ll d[N][N], n, m, q;

int main() {
  memset(d, 0x3f, sizeof d);
  cin >> n >> m >> q;
  for (int i=1;i<=m;++i) {
    ll u, v, w;
    cin >> u >> v >> w;
    d[u][v] = min(d[u][v], w);
  }
  // 排除自环 距离为0
  for (int i=1;i<=n;++i) {
    d[i][i]=0;
  }
  

  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]);
      }
    }
  }

  while (q--) {
    int u, v;
    cin >> u >> v;
    cout << (d[u][v] >= inf ? -1 : d[u][v]) << '\n';
  }
}

分层图最短路

分层图图大小为k*n，一定要注意数据范围！！！
以洛谷 P4568 [JLOI2011] 飞行路线为例。
观察数据范围，，所以将图分层是可行的。那么接下来就建k+1层图，每层图正常建边与原图相同，层与层之间用权值为0的边相连，建好后用最短路算法就可解决。

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> k;
  int s, t;
  cin >> s >> t;

  int a, b, c;
  for (int i = 0; i < m; ++i) {
    cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
    for (int j = 1; j <= k; ++j) {
      g[a+(j-1) * n].push_back({b+j*n, 0});
      g[b+(j-1)* n].push_back({a+j*n, 0});

      g[a + j * n].push_back({b + j * n, c});
      g[b+j*n].push_back({a+j*n, c});
    }
  }
  for (int i = 1; i <= k; ++i) {
    g[t+(i-1)*n].push_back({t+i*n, 0});
  }
  dijkstra(s);
  cout << d[t + k * n];
}

分层图的核心理念：

将点拆开，复制多层图，并利用特殊构造的边将各层相连的建图方法。
一般用于边或点有特殊限制问题（如重复经过次数，多种价值选择等）
需要保证拆开后的总点数规模可接受。
补充分层图加网络最大流问题

最小生成树(MST)
生成树：连通图中，找出一个节点最多的（n点），n-1条边的子连通图。
最小是指在生成树中找到权值和最小的
以下图为例：
1
2
3
4
5
6
7
graph LR
1---|2|2
1---|3|4
2---|3|3
2---|1|4
3---|4|5
4---|5|5
则最小生成树（虚线连接）为：
1
2
3
4
5
6
7
graph LR
1-.-|2|2
1---|3|4
2-.-|3|3
2-.-|1|4
3-.-|4|5
4---|5|5
基于点的Prim算法（稠密图）
1
2
3
4
5
6
7
graph LR
1---|1|2
1---|3|4
2---|2|3
2---|1|4
3---|5|5
4---|3|5

两个集合intree和outtree
选1号点作为起点放入intree，移出outtree（以下步骤同理）
循环n-1次，每次确定一条边，在所有点当中找离intree中的点距离最近的点，将其加入intree，更新所有点到intree任意一点的最短距离。

在权值均为正的情况下，使用邻接表只需考虑intree集合中的点直接连接的点。
如果使用邻接矩阵，非直接连接的点距离初始化为无穷大即可。

朴素

#include <bitset>
#include <cstring>
#include <iostream>
using namespace std;
using ll = long long;
const int N = 1e3 + 10;
const ll inf = 4e18, p = 998244353;

int a[N][N], d[N];
bitset<N> intree;
int main() {
  int n, m;
  cin >> n >> m;
  memset(a, 0x3f, sizeof a);
  memset(d, 0x3f, sizeof d);
  for (int i = 1; i <= n; ++i) {
    a[i][i] = 0;
  }

  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    // 排除无向图出现重边
    a[u][v] = min(a[u][v], w);
    a[v][u] = min(a[v][u], w);
  }

  ll ans = 0;

  for (int i = 1; i <= n; ++i) {
    int u = 1; // u就是距离intree点最近的点
    for (int j = 1; j <= n; ++j) {
      if (intree[u] || (!intree[j] && d[j] < d[u]))
        u = j;
    }
    if (d[u] < 0x3f)
      ans += d[u];
    intree[u] = 1;
    d[u] = 0;
    for (int j = 1; j <= n; ++j) {
      if (intree[j])
        continue;
      d[j] = min(d[j], a[u][j]);
    }
  }
  cout << ans;
}

堆优化

#include <bitset>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
const ll inf = 4e18, p = 998244353;

struct Edge {
  ll x, w;
  bool operator<(const Edge &u) const {
    return w ==u.w?x<u.x:w>u.w;
  }
};
vector<Edge> g[N];
ll d[N];
bitset<N> intree;

int main() {
  int n, m;
  cin >> n >> m;
  memset(d, 0x3f, sizeof d);

  for (int i = 1; i <= m; ++i) {
    ll u, v, w;
    cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  ll ans = 0;
  priority_queue<Edge> pq;

  pq.push({1, 0});
  d[1] = 0; 
  while (pq.size()) {
    // auto [x, w] = pq.top();
    int x = pq.top().x;
    pq.pop();
    if (intree[x])
      continue;
    intree[x] = 1;
    // ans += w;
    ans += d[x];
    d[x] = 0;

    for (auto &[y, w] : g[x]) {
      if (!intree[y] && w < d[y]) {
        d[y] = w;
        pq.push({y, w});
      }
    }
  }

  for (int i=1;i<=n;++i) {
    if (!intree[i]) ans = -1;
  }
  
  cout << ans << '\n';
}

基于边的Kruskal算法（稀疏图）

贪心、排序 $并查集$

给边从小到大排序

从小到大选边，若这条边的两个已经连通就跳过，若未连通就选上并连通。

#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const ll inf = 4e18, p = 998244353;
ll d[N];
int pre[N];
int root(int x) {
  return pre[x] = (pre[x] == x ? x : root(pre[x]));
}

struct Edge {
  ll u, v, w;
  bool operator<(const Edge &m) const {
    return w == m.w ? (u==m.w?v<m.v:u<m.w) : w < m.w;
    // return w<m.w;
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  memset(d, 0x3f, sizeof d);

  vector<Edge> es;
  for (int i=1;i<=m;++i) {
    ll u, v, w;cin >> u>> v>> w;
    es.push_back({u, v, w});
  }

  sort(es.begin(), es.end());
  ll ans = 0;
  for (int i=1;i<=n;++i) {
    pre[i] = i;
  }

  for (auto &[u, v, w] : es) {
    if (root(u) == root(v))
      continue;
    ans += w;
    pre[root(u)] = root(v);
  }
  for (int i=1;i<n;++i) {
    if (root(i) != root(i+1)) ans = -1;
  }
  cout << ans;
}

并查集

Dijkstra单源最短路

Floyd多源最短路

分层图最短路

最小生成树(MST)

基于点的Prim算法（稠密图）

基于边的Kruskal算法（稀疏图）