一般最短路 Floyd 传递闭包 可以使用 bitset 优化： 例题：洛谷 P4306[JSOI2010]连通数 题目大意： 给一个 $n$ 个点的有向图，其连通数指图中可达顶点对个的个数（包括自己和自己）。求图中的连通数 问题分析： 可以直接 Floyd 传递闭包搞。 如果上面做法被卡，可以先用 Tarjan 缩点，然后在 DAG 上 BFS …

强连通分量 题目：P3387 缩点 题目大意： 给定一个 $n$ 个点 $m$ 条边有向图，每个点有一个权值，求一条路径，使路径经过的点权值之和最大。你只需要求出这个权值和。 允许多次经过一条边或者一个点，但是，重复经过的点，权值只计算一次。 分析: 先使用 tarjan 缩点，然后对图进行重构，再对拓扑图记忆化搜索。 #include <b…

#include <bits/stdc++.h> typedef long long ll; using namespace std; const int N = 1e4 + 50; const int M = 2e5 + 50; const int INF = 1e9; int n, m, S, T; int head[N], tot…

最大权闭合子图 定义：有一个有向图，每一个点都有一个权值（可以为正或负或 $0$），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。 解法： 这个问题可以转化为最小割问题，用网络流解决。 从源点 $S$ 向每个正权点连一条容量为权值的边，每个负权点向汇点 $T$ 连一条容量为权值的绝对值的边，有向图原来的边容量全…

二分图最大匹配 匈牙利算法 #include <bits/stdc++.h> using namespace std; const int N = 1005; int n, m, k; int tot, head[N]; struct Edge { int nex, to; }e[N * N]; void add(int a,int b…

二分图最大权完美匹配：KM算法 KM算法只适用于一定存在完美匹配的情形。 洛谷P6577 【模板】二分图最大权完美匹配 题目描述 给定一张二分图，左右部均有 $n$ 个点，共有 $m$ 条带权边，且保证有完美匹配。 求一种完美匹配的方案，使得最终匹配边的边权之和最大。 输入格式 第一行两个整数 $n,m$；第 $2\sim m+1$ 行，每行三个整…

问题 P3381 【模板】最小费用最大流 题目描述 给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。 输入格式 第一行包含四个正整数 $N,M,S,T$，分别表示点的个数、有向边的个数、源点序号、汇点序号。 接下来 $M$ 行每行包含四个正整数 $u_i,v_i,w_i,f_i$，表…

Prufer 序列 定义 Prufer 序列可以将一个带标号 $n$ 个结点的树用 $[1,n]$ 中的 $n-2$ 个整数表示。可以把它理解为完全图的生成树与数列之间的双射。 建立方法：每次选择一个编号最小的叶结点并删掉它，然后在序列中记录下它连接到的那个结点。重复 $n-2$ 次后就只剩下两个结点，算法结束。 性质 在构造完 Prufer 序列…

题目大意 给定一个 $n$ 个点 $m$ 条边的带标号无向图，它有 $k$ 个连通块，求添加 $k-1$ 条边使得整个图连通的方案数，答案对 $p$ 取模。$(1 \le n \le 10^5, 0 \le m \le 10^5, 1 \le k \le 10^9)$ 解题思路 设 $s_i$ 为第 $i$ 个连通块的点数， $d_i$ 为第 $i…