算法
库函数
next_permutation(start,end) prev_permutation(start,end) (全排列函数)
[库函数介绍](C++中全排列函数next_permutation 用法-CSDN博客)
[库函数原理](C++中next_permutation函数的使用方法、原理及手动实现_c++ next_permutation-CSDN博客)
库函数原理基本解释:
因为在一个全排列中全为降序是最大的，此时就需要找到前面的一个数（即第一个小于的数），然后进行上述过程，而在新开的排列中，要把后面的序列仍未降序，翻转一下即可
[洛谷P1706 全排列问题](P1706 全排列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
//模拟next_permutation()(贪心)
#include<iostream>
using namespace std;
const int N=10;
int n;
int a[N];
bool next_permutation(){
int k=n-1;
while(k&&a[k-1]<a[k]) k--;//从右往左找第一个不为降序的
if(!k) return false;//没有找到，序列已经为最大
int t=k;
while(t<n&&a[t]>a[k-1]) t++;//找到降序序列中大于a[k-1]的最小的一个
t--;
swap(a[k-1],a[t]);
reverse(a+k,a+n);
return true;
}
int main(){
cin>>n;
for(int i=0;i<n;i++) a[i]=i+1;
do{
for(int i=0;i<n;i++) cout<<" "<a[i];
}while(next_permutation());
reutrn 0;
}
nth_element （求第k小值）
stl,o(n),常数较大
[具体用法](STL 之 nth_element详解-CSDN博客)
next(it,num),prev(it,num)
next(it,num),迭代器it的后num的迭代器，prev则相反(num可为负数)
min_element(begin(),end()),max_element(begiin(),end()) (取最小值最大值)
返回的是指针
_int128的输入输出
由于c++的输入输出不支持_int128,以下是_int128的输入输出板子
#include <bits/stdc++.h>
using namespace std;
inline __int128 read(){
__int128 x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void print(__int128 x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
int main(void){
__int128 a = read();
__int128 b = read();
print(a + b);
cout << endl;
return 0;
}
STL
list
[基本用法](C++ STL标准库： std::list使用介绍、用法详解-CSDN博客)
sort([cmp]),unique
数据结构
单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;
}
单调队列
常见模型：找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
while (hh <= tt && check_out(q[hh])) hh ++ ; // 判断队头是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;
}
对顶堆
动态维护一个序列上第$k$大的数，$k$的值可能会发生变化。
对于这类问题，可以用对顶堆来解决（避免写权值线段树的繁琐）
对顶堆由一个大根堆和一个小根堆组成，小跟堆维护大值即前$k$大的值，大跟堆维护小值即比第$k$大数小的其它数
支持以下操作：
- 维护：当小根堆的大小小于$k$时，不断将大根堆堆顶元素取出并插入小根堆，直到小根堆的大小等于$k$；当小根堆的大小大于$k$时，不断将小根堆堆顶元素取出并插入大根堆，直到小根堆的大小等于$k$；
- 插入元素：若插入的元素大于等于小根堆堆顶元素，则将其插入小根堆，否则将其插入大根堆，然后维护对顶堆；
- 查询第$k$大元素：小根堆堆顶元素即为所求；
- $k$值$+1/-1$：根据新的$k$值维护对顶堆；
链表
单链表
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int r[N], val[N], pos[N], idx = 1;//r存其右面的数，val存值，pos存元素地址
val[idx] = x, r[idx] = r[0], r[0] = idx++;//头插法
val[idx] = x, r[idx - 1] = idx++;//顺序插入
r[x] = r[r[x]]; //将x右边的元素删除
val[idx] = y, r[idx] = r[pos[x]], r[pos[x]] = idx++;//将元素y插入到元素x右面
双向链表
int r[N], l[N], val[N], pox[N], idx = 1;
r[idx - 1] = idx, l[idx] = idx - 1, idx++;//顺序插入
pre = pox[x], val[idx] = y, pox[y] = idx, r[idx] = r[pre], l[idx] = pre, l[r[pre]] = idx, r[pre] = idx++;//将元素y插入到x右面
p = pos[x], r[l[p]] = r[p], l[r[p]] = l[p];//将元素x删除
for (int i = r[1]; i; i = r[i]) cout << val[i] << " ";//遍历元素
//尾结点和头结点都是0
y总模版
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
// 初始化
void init()
{
head = -1;
idx = 0;
}
// 在链表头插入一个数a
void insert(int a)
{
e[idx] = a, ne[idx] = head, head = idx ++ ;
}
// 将头结点删除，需要保证头结点存在
void remove()
{
head = ne[head];
}
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;
// 初始化
void init()
{
//0是左端点，1是右端点
r[0] = 1, l[1] = 0;
idx = 2;
}
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
e[idx] = x;
l[idx] = a, r[idx] = r[a];
l[r[a]] = idx, r[a] = idx ++ ;
}
// 删除节点a
void remove(int a)
{
l[r[a]] = l[a];
r[l[a]] = r[a];
}
树状数组
1.性质
1.x的父节点是x+lowbit(x)
2.每个x代表的区间长度为lowbit(x)，[x-lowbit(x)+1,x]
3.每个tri[x]由b[x],tri[x-20],tri[x-21]...(2k<lowbit(x),xk+1>=lowbit(x+1))
2.树状数组的o(N) 建树方法
由于每个tr[i]都是以i为结尾，长度为lowbit(i)的区间的和，故可预处理前缀和进行o(N)建树
int sums[N],tri[N];//sums是前缀和
for(int i=1;i<=n;i++) tri[i]=sums[i]-sums[i-lowbit(i)];
3.树状数组维护区间最值
void update(int x, int c) {//(logn)^2 单点修改
b[x] = c;
int lx;
while (x <= n) {
tri[x] = b[x];
lx = lowbit(x);
for (int i = 1; i < lx; i <<= 1)
tri[x] = max(tri[x], tri[x - i]);
}
}
int query(int l, int r) {//(logn)^2 区间查询
int ans = 0;
while (l <= r) {
ans = max(ans, b[r]);
for (r--; r - lowbit(r) >= l; r -= lowbit(r))//这样的写法不会死循环
ans = max(tri[r], ans);
}
return ans;
}
线段树
线段树是一颗二叉树，节点数为2n-1，可以以O(log n)的操作进行单点修改，区间修改，区间查询(区间修改和区间查询大概为4log n,常数比树状数组大,懒标记由于此性质就可优化为O(log n))
线段树维护的是区间，即是线段，而不是点，要注意
注意事项 ：要开4N的空间（因此有时候要离散化以压缩空间）,证明如下 csdn证明
1.单点修改，区间查询
题目链接[P3374 【模板】树状数组 1](P3374 [模板]树状数组 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 5e5 + 10;
typedef long long ll;
int w[N];
int n, m;
struct Node {
int l, r;
ll sum;
}tr[N*4];
void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r) {
if (l == r) tr[u] = { l,r,w[l] };
else {
tr[u] = { l,r };
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int x, int d) {//更新
if (tr[u].l == x && tr[u].r == x) tr[u].sum += d;
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(u << 1, x, d);
else modify(u << 1 | 1, x, d);
pushup(u);
}
}
ll query(int u, int l, int r) {、、查询
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else {
int mid = tr[u].l + tr[u].r >> 1;
ll res = 0;
if (l <= mid) res = query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
}
int main() {
scanf("%d%d", &n,&m);
for (int i = 1; i <= n; i++) cin >> w[i];
build(1, 1, n);
while (m--) {
int op, x, y;
scanf("%d%d%d", &op, &x, &y);
if (op == 1) modify(1, x, y);
else printf("%d\n", query(1, x, y));
}
return 0;
}
2.区间修改，区间查询（涉及懒标记，即add)
加上懒标记的节点sum会维护上，但其子节点的sum和add不会维护上，当查询或修改涉及一个节点是，需要其父节点进行pushdown操作，这样就可以维护该节点的sum和add了
题目链接[P3372 【模板】线段树 1](P3372 [模板]线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
int w[N], n, m;
struct Node {
int l, r;
ll sum, add;//add即为懒标记
}tr[N * 4];
inline void pushup(int u) {
tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
inline void pushdown(int u) {
auto& root = tr[u], &right = tr[u << 1 | 1], &left = tr[u << 1];
if (root.add) {
left.add += root.add, left.sum += (ll)(left.r - left.l + 1) * root.add;
right.add += root.add, right.sum += (ll)(right.r - right.l + 1) * root.add;
root.add = 0;
}
}
void build(int u, int l, int r) {
if (l == r) tr[u] = { l,r,w[l],0 };
else {
tr[u] = { l,r };
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
void modify(int u, int l, int r, int d) {
if (tr[u].l >= l && tr[u].r <= r) { //由于只要该区间属于要修改的区间就立即返回(并加上懒标记)，所以modify可做到log n
tr[u].sum += (ll)(tr[u].r - tr[u].l + 1) * d;
tr[u].add += d;
}
else {
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, d);
if (r > mid) modify(u << 1 | 1, l, r, d);
pushup(u);
}
}
ll query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
else {
pushdown(u);
ll res = 0;
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) res += query(u << 1, l, r);
if (r > mid) res += query(u << 1 | 1, l, r);
return res;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", w + i);
build(1, 1, n);
while (m--) {
int op, x, y, k = 0;
cin >> op >> x >> y;
if (op == 1) {
scanf("%d", &k);
modify(1, x, y, k);
}
else printf("%lld\n", query(1, x, y));
}
return 0;
}
3.扫描线法(用于解决多个矩形的面积（可能相交）)，[详解见]一文读懂扫描线算法 - 知乎 (zhihu.com))
题目链接[acwing247. 亚特兰蒂斯](247. 亚特兰蒂斯 - AcWing题库)
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
const int N = 10010;
struct Segment {
double x, y1, y2;
int cnt;
bool operator<(const Segment& t) const {
return x < t.x;
}
}seg[2 * N];;
vector<double> ys;
struct Node {
int l, r, cnt;
double len;
}tr[8 * N];
int n;
inline void pushup(int u) {
if (tr[u].cnt) tr[u].len = ys[tr[u].r + 1] - ys[tr[u].l];
else if (tr[u].l != tr[u].r) {
tr[u].len = tr[u << 1].len + tr[u << 1 | 1].len;
}
else tr[u].len = 0;
}
inline int find(double x) {
return lower_bound(ys.begin(), ys.end(), x) - ys.begin();
}
void build(int u, int l, int r) {
tr[u] = { l,r,0,0 };
if (l != r) {
int mid = l + r >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
}
void modify(int u, int l, int r, int k) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].cnt += k;
pushup(u);
}
else {
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) modify(u << 1, l, r, k);
if (r > mid) modify(u << 1 | 1, l, r, k);
pushup(u);
}
}
int main() {
int T = 1;
while (scanf("%d", &n), n) {
ys.clear();
for (int i = 0, j = 0; i < n; i++) {
double x1, x2, y1, y2;
scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
seg[j++] = { x1,y1,y2,1 }, seg[j++] = { x2,y1,y2,-1 };
ys.push_back(y1), ys.push_back(y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
build(1, 0, ys.size() - 2);
sort(seg, seg + 2 * n);
double res = 0;
for (int i = 0; i < 2 * n; i++) {
if (i) res += tr[1].len * (seg[i].x - seg[i - 1].x);
modify(1, find(seg[i].y1), find(seg[i].y2) - 1, seg[i].cnt);
}
printf("Test case #%d\n", T++);
printf("Total explored area: %.2f\n\n", res);
}
return 0;
}
[可解决的问题的一些板子](线段树(Segment Tree)(上) - 知乎 (zhihu.com))
可持久化线段树
[较详细介绍](算法学习笔记(50): 可持久化线段树 - 知乎 (zhihu.com))
[acwing 255.第k小数](255. 第K小数 - AcWing题库)(非严格第k小数)
将数值大小作为线段，用线段树维护数值数目，假设求0到r区间的第k小数，先求0到Mid(Mid=(0+r)/2)的数值数目cnt，若k<cnt，则递归到区间0到Mid继续求解，反之则递归到Mid到r。若想求l到r区间的第k小数，则先求0到r中的数值数目与0到l-1的数值数目之差，下续操作与上面相同，维护历史版本则需要可持久化线段树
//这题是静态主席树（不涉及点的修改）
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N];
vector<int> nums;//离散化
struct Node{
int l,r;//这里是左右二子节点
int cnt;
}tr[N*4+N*17];//N*4是最初版本的空间，后面每一次版本需要log(n)的空间，所以再加上N*log(N)
int root[N],idx;//root存储每个历史版本的根节点，idx用于计数
inline int find(int x){
return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
int build(int l,int r){ //返回节点
int p=++idx;//创建新节点
if(l==r) return p;
int mid=l+r>>1;
tr[p].l=build(l,mid),tr[p].r=build(mid+1,r);
return p;
}
int insert(int p,int l,int r,int x){
int q=++idx;//创建新节点
tr[q]=tr[p];//继承上一个版本对应的节点
if(l==r){
tr[q].cnt++;
return q;
}
int mid=l+r>>1;
if(x<=mid) tr[q].l=insert(tr[q].l,l,mid,x);//如果x小于mid，那么p的左儿子将会发生改变
else tr[q].r=insert(tr[q].r,mid+1,r,x);
tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;//更新tr[q].cnt
return q;
}
int query(int q,int p,int l,int r,int k){//二分搜索
if(l==r) return l;
int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;//左边部分的cnt
int mid=l+r>>1;
if(k<=cnt) return query(tr[q].l,tr[p].l,l,mid,k);//在左半边找
else return query(tr[q].r,tr[p].r,mid+1,r,k - cnt);
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
nums.emplace_back(a[i]);
}
sort(nums.begin(),nums.end());//离散化
nums.erase(unique(nums.begin(),nums.end()),nums.end());
root[0]=build(0,nums.size()-1);//先创建一个最初版本，后面形状不会再发生变化
for(int i=1;i<=n;i++) root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));//每个版本由他前一个版本更新而来
while(m--){
int l,r,k;
cin>>l>>r>>k;
cout<<nums[query(root[r],root[l-1],0,nums.size()-1,k)]<<endl;
}
return 0;
}
字符串
KMP
时间复杂度通常为o(n+m),最坏为o(2n)
代码模版
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int nex[N];
string s1, s2;
int main() {
cin >> s1 >> s2;
s1 = " " + s1, s2 = " " + s2;
for (int i = 2, j = 0; i < s2.size(); i++) {
while (j && s2[i] != s2[j + 1]) j = nex[j];
if (s2[i] == s2[j + 1]) j++;
nex[i] = j;
}
for (int i = 1, j = 0; i < s1.size(); i++) {
while (j && s1[i] != s2[j + 1]) j = nex[j];
if (s1[i] == s2[j + 1]) j++;
if (j == s2.size() - 1) {
cout << i - s2.size() + 2 << endl;
j = nex[j];//进行下一次匹配
}
}
for (int i = 1; i < s2.size(); i++) cout << nex[i] << " ";
return 0;
}
给你一个字符串 s1，它是由某个字符串 s2 不断自我连接形成的（保证至少重复 2 次）。但是字符串 s2 是不确定的，现在只想知道它的最短长度是多少。
答：n-next[n]
using ull=unsigned long long;
using pll=pair<ull,ull>;
const ull mod=1e9+7,P=131;
string s;
set<pll> hask;
ull p1[N],hask1[N],hask2[N],p2[N];
void init(){
p1[0]=1;
for(int i=1;i<N;i++) p1[i]=p1[i-1]*P;
p2[0]=1;
for(int i=1;i<N;i++) p2[i]=p2[i-1]*P%mod;
}
void init1(){
hask1[0]=hask2[0]=0;
for(int i=1;i<s.size();i++)
hask1[i]=hask1[i-1]*P+s[i];
for(int i=1;i<s.size();i++)
hask2[i]=(hask2[i-1]*P+s[i])%mod;
}
ull get1(int l,int r){
return hask1[r]-hask1[l]*p1[r-l+1];
}
ull get2(int l,int r){
return ((hask2[r]-(hask2[l]*p2[r-l+1]%mod))%mod+mod)%mod;
}
最长回文串
1.二分加字符串哈希
下面计算了字符串的回文串个数，稍加修改即可计算最长回文串
时间复杂度：O(nlogn)
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010, P = 131;
#define endl '\n'
using ull = unsigned long long;
int n, ans;
ull h[N], hask1[N], hask2[N];
char s[N];
ull gethask1(int l, int r) {
return hask1[r] - hask1[l - 1] * h[r - l + 1];
}
ull gethask2(int l, int r) {
return hask2[l] - hask2[r + 1] * h[r - l + 1];
}
int query1(int x) {//奇数长度
int l = 0, r = min(x, n - x);//二分回文字符串长度
while (l < r) {
int mid = l + r + 1 >> 1;
if (gethask1(x - mid, x) == gethask2(x, x + mid)) l = mid;
else r = mid - 1;
}
return r;
}
int query2(int x) {//偶数长度
int l = 0, r = min(x, n - x);
while (l < r) {
int mid = l + r + 1>> 1;
if (gethask1(x - mid + 1, x) == gethask2(x + 1, x + mid)) l = mid;
else r = mid - 1;
}
return r;
}
int main() {
cin >> s + 1;
n = strlen(s + 1);
h[0] = 1;
for (int i = 1; i <= n; i++) {
hask1[i] = hask1[i - 1] * P + s[i];
h[i] = h[i - 1] * P;
}
for (int i = n; i >= 1; i--) hask2[i] = hask2[i + 1] * P + s[i];
for (int i = 1; i <= n; i++)
ans += query1(i) + query2(i);
cout << ans + n << endl;//序列中每个单独的字符也是一个回文串，所以要加上n
return 0;
}
对上面的代码去除二分，再在每个字符之间加上#（类似manacher算法），可在O(n)的时间内求出最长回文串
unsigned long long order1[2000100], order2[2000100];
unsigned long long pwd[2000100], base = 13331;
char s[2000100];
char s2[2000100];
int ct = 1;
unsigned long long gethash1(int l, int r)
{
return order1[r] - order1[l - 1] * pwd[r - l + 1];
}
unsigned long long gethash2(int l, int r)
{
return order2[l] - order2[r + 1] * pwd[r - l + 1];
}
int main()
{
pwd[0] = 1;
for (int i = 1; i <= 1000000; i++)
pwd[i] = pwd[i - 1] * base;
int CASE = 1;
while (~scanf("%s", s))
{
if (!strcmp(s, "END"))
break;
printf("Case %d: ", CASE++);
int len = strlen(s);
ct = 1;
s2[ct++] = '#';
for (int i = 0; i < len; i++)
{
s2[ct++] = s[i];
s2[ct++] = '#';
}
len = ct - 1;
order1[0] = order2[len + 1] = 0;
for (int i = 1; i <= len; i++) //正哈希
order1[i] = order1[i - 1] * base + s2[i];
for (int i = len; i >= 1; i--) //逆哈希
order2[i] = order2[i + 1] * base + s2[i];
int maxx = 0;
for (int i = 1; i <= len; i++) //On求最长回文子串
while (i - maxx >= 1 && i + maxx <= len &&
gethash1(i - maxx, i + maxx) == gethash2(i - maxx, i + maxx))
maxx++;
printf("%d\n", maxx - 1);
}
return 0;
}
图论
最短路
前置知识
求最短路时，往往分为四种类型
- bfs：边的权值都相同
- 双端队列bfs：边的权值只有$0$和$x$两种
- dp：拓扑图
- 以下知识：有环皆权值不符合上面
1.堆优化dijkstra
const int N = 1e4 + 10, M = 5e5 + 10;
using pii = pair<int, int>;
using ll = long long;
int h[N], e[M], ne[M], idx = 1, w[M];
priority_queue<pii, vector<pii>, greater<pii>> q;
int n, m, s;
ll dist[N];
bool st[N];
inline void add(int a, int b, int c) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
void dijkstra() {
for (int i = 1; i <= n; i++) dist[i] = (1ll << 31) - 1;
dist[s] = 0;
q.push({ dist[s],s });
while (q.size()) {
auto t = q.top();
q.pop();
ll distance = t.first, ver = t.second;
if (st[ver]) continue;//冗余
st[ver] = true;
for (int i = h[ver]; i; i = ne[i]) {
int j = e[i];
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i];
q.push({ dist[j],j });
}
}
}
}
多到一最短路：反向建边用dijkstra
[最短路，最长路，次短路](最短路 || 最长路 || 次短路 - Poetic_Rain - 博客园 (cnblogs.com))
多源最短路
Floyd 算法(n3)
是用来求任意两个结点之间的最短路的。
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有负环）
具体描述见oiwiki
代码如下
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++) g[i][i]=0;
for(int k=1;k<=n;k++)//必须在最外层
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
Floyd 算法的扩展
1.传递闭包
给定n个元素，m个传递关系（边)，判断两个点之间的传递关系（或是否矛盾）
- 题1：[传递闭包模版题](B3611 [模板]传递闭包 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
思路：判断两点是否联通，做一遍稍微修改的floyd就ok（其实用dfs，o(n2)就能做到）
for(int k=1;k<=n;k++)//必须在最外层
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]|=g[i][k]&g[k][j];
该题用bitset还有o(n2)的做法，思想是状态压缩，i能到k，则k能到的点i都能到
bitset<n> g[n];
for(int k=1;k<=n;k++) //最外层
for(int i=1;i<=n;i++)
if(g[i][k]) g[i]|=g[k];
-
题2：给定n个点，m个关系（a>b），判断是否矛盾，如果不矛盾，则判断是否能确定每个点的大小关系
思路：跑一遍floyd,如果存在g[a][a] = 1,则存在矛盾（a不可能大于它本身）,如果存在g[a][b] = g[b][a] = 0,则为无法确定，反之则为可确定
2.最小环
大概形容：假设有一个最小环，它里面的点肯定有一个最大编号k，此时枚举i，j（i，j != k）,g[i][k]和g[k][j]是已经确定的，g[i][j]取最小即为不包括点k的最小值，枚举到最小的g[i][k]+g[k][j]+g[i][k]就是这个最小环（i，j可能会重复，最小环节点数目大于等于2）
那么就可以将集合划分为k个，每个的定义为 里面点的最大编号为i(0 < i <=k)，那么这个集合中肯定包含上面提到的最小环，当floyd运行到第m阶段开始时，此时g[i][j]为第m-1时的大小，直接枚举i，j，然后计算最小环
for (int k = 1; k <= n; k++) {
for (int i = 1; i < k; i++)
for (int j = i + 1; j < k; j++) {//若最小环不小于三个节点，i!=j即可
if (ll(d[i][j]) + a[i][k] + a[k][j] < ans) {//注意这边是a
ans = d[i][j] + a[i][k] + a[k][j];
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (d[i][j] > d[i][k] + d[k][j]) {
d[i][j] = d[i][k] + d[k][j];
pos[i][j] = k;//计算路径，可据此输出最小环（递归）
}
}
3.floyd的增量问题
-
问题背景：如果已经跑了一遍floyd，此时修改了某条边，此时计算新的多源最短路
-
思路：直接去想是再跑一边floyd，但会复杂度角高，因为这条边被修改，所以只有走了这条边，两点之间的最短路才有可能改变，故只需枚举i，j，更新即可，o(n2)
-
例题：[传送门]([P6464 传智杯 #2 决赛] 传送门 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
#include<bits/stdc++.h>
const int INF = 0x3f3f3f3f;
using namespace std;
const int maxn = 1e105;
int dp[maxn][maxn];//抄袭有奖qaq
int main(){
int n, m;
scanf("%d %d", &n, &m);
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(i == j) dp[i][j] = 0;
else dp[i][j] = INF;
int u, v, w;
for(int i = 0; i < m; i ++)
{
scanf("%d %d %d", &u, &v, &w);
//建立双向边
dp[u][v] = w;
dp[v][u] = w;
}
//floyd 算法
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
//假设假设建立传送门的点对为（i，j）(默认j > i)，枚举减少的距离任意一个点对点（a, b）（这里默认b > a）距离为
int ans = INF, res;
for(int i = 1; i < n; i ++)
for(int j = i + 1; j <= n; j ++)
{
res = 0;
for(int a = 1; a < n; a ++)
for(int b = a + 1; b <= n; b ++)
if(a != i || b != j)
res += min(dp[a][b], min(dp[a][i] + dp[j][b], dp[a][j] + dp[i][b]));//这道题更新的边为零，故省略了dp[i][j]和dp[j][i]
ans = min(ans, res);
}
printf("%d\n", ans);
return 0;
}
4.有限制的floyd
先来看一道例题[牛站](345. 牛站 - AcWing题库)
题意如下：给定一张由 T 条边构成的无向图，点的编号为 1~1000之间的整数，求从起点 S 到终点 E恰好经过 N 条边（可以重复经过）的最短路。
- 前情提要：普通的floyd似乎对这类题无法下手，但有限制的floyd便可以解决这类问题
先来看什么是有限制的floyd
static int temp[N][N];
memset(temp, 0x3f, sizeof temp);
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);//a代表步数为k1,b代表步数为k2,则temp代表步数为k1+k2
memcpy(c, temp, sizeof temp);
我们发现做一次类Floyd好像不用并不会去用该次的结果（a,b数组存储上一次的结果）自我更新，只会用上一次的结果来更新一次，不像Floyd那样可以自己更新自己多
有限制的floyd具有结合律，故temp代表的步数就是a与b的步数之和，又因为具有结合律，所以可用快速幂的思想将o(Nn3)优化为o(logNN3)
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
const int N = 210;
int res[N][N], g[N][N];//g刚开始代表经过一条边
int k, n, m, S, E;
map<int, int> id;
void mul(int c[][N], int a[][N], int b[][N]) {
static int temp[N][N];
memset(temp, 0x3f, sizeof temp);
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);//a代表步数为k1,b代表步数为k2,则temp代表步数为k1+k2
memcpy(c, temp, sizeof temp);
}
void qmi() {//符合结合律，可使用类似快速幂的思想
memset(res, 0x3f, sizeof res);
for (int i = 1; i <= n; i++) res[i][i] = 0;//代表经过零条边
while (k) {
if (k & 1) mul(res, res, g);//res+=g;
mul(g, g, g);//g<<1
k >>= 1;
}
}
int main() {
cin >> k >> m >> S >> E;
memset(g, 0x3f, sizeof g);
if (!id.count(S)) id[S] = ++n;
if (!id.count(E)) id[E] = ++n;
S = id[S], E = id[E];
while (m--) {
int a, b, c;
cin >> c >> a >> b;
if (!id.count(a)) id[a] = ++n;
if (!id.count(b)) id[b] = ++n;
a = id[a], b = id[b];
g[a][b] = g[b][a] = min(g[a][b], c);//代表经过一条边
}
qmi();
cout << res[S][E] << endl;
return 0;
}
最长路
由于不符合最优子结构无法使用dijkstra,可以用spfa(取反求最短路或改松弛条件为>)
如果全为负可用dijkstra(取反用最短路即可)
相乘的最长路如果符合子结构（例如边权0<w<1），可用dijkstra，否则用spfa
总结：1.spfa 2.拓扑排序(无环可用)上面链接有代码
次短路及k短路
次短路
次短路分为严格次短路和非严格次短路，又可分为边可重复次短路和边不可重复次短路
-
边不可重复的严格最短路(n2logm)
[P1491 集合位置](P1491 集合位置 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
思路：采用删边法。
我们先对原先的图跑一边最短路，记录最短路的路径。
之后每次删去最短路的一条边，重新跑最短路，在这几次跑出来的结果中，取最小值，就是最终答案。正确性证明：
显然，次短路和最短路的路径必然不是相同的。
因为最短路的路径肯定是整张图中最优的，我们每次去掉最短路上的一条路径，剩下的路径必然不会比最短路的路径更优。
在删掉一条边后的剩下的路径中取得最短路径，且肯定不会比原先图的最短路径更优，那么这一条路就必然是次短路径。较为简单，代码不贴
-
边不可重复的非严格最短路(n2logm)
思路和上面相同，只要求出最短的且满足且不等于最短路就行
-
边可重复的严格和非严格最短路((m+n)logm)
思路：用两个 dist 数组，分别记录最短路和次短路。
当最短路可以更新时，那么次短路就继承之前的最短路的长度。
当次短路可以更新，且次短路更新后不会超过最短路长度，那么次短路更新若这道题要求非严格次短路，只需将当次短路可以更新时的后半部分条件稍作修改即可（
dist[v][1]<dis_now+w改成dist[v][1]<=dis_now+w）[[USACO06NOV] Roadblocks G]([P2865 USACO06NOV] Roadblocks G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
void dijkstra(){ memset(dist,0x3f,sizeof(dist)); dist[1][1] = 0; q.push((point){1,0}); while (!q.empty()){ int tmp = q.top().id; int dis_now = q.top().dis; q.pop(); for (int i = head[tmp];i;i = e[i].nxt){ int v = e[i].to; int w = e[i].w; if (dist[v][1] > dis_now + w){ dist[v][2] = dist[v][1]; dist[v][1] = dis_now + w; q.push((point){v,dist[v][1]}); q.push((point){v,dist[v][2]}); } else if (dist[v][2] > dis_now + w && dist[v][1] < dis_now + w){ dist[v][2] = dis_now + w; q.push((point){v,dist[v][2]}); } } } }//a*也可做
k短路（Astar）(knlogn)
Astar算法可用于求k短路（边可重复），因为该问题搜索空间很大且知道终点，所以适合Astar算法
注意：还可以用于求次短路(严格和不严格)
先反向求一遍所有节点到n的最短路dist[i],以将其作为预估函数
先出队的一定优于后出队的（不再证明），因此n出队k次后即为k短路
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
typedef pair<int, PII> PIII;
const int N = 1010, M = 200010;
int n, m, S, T, K;
int h[N], rh[N], e[M], w[M], ne[M], idx = 1;//建立一个反向头结点方便反向建边
int dist[N], cnt[N];
bool st[N];
void add(int h[],int a,int b,int c)
{
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx++;
}
void dijkstra()
{
priority_queue<PII,vector<PII>,greater<PII>> heap;
heap.push({0,T});//终点
memset(dist, 0x3f, sizeof dist);
dist[T] = 0;
while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y;
if(st[ver]) continue;
st[ver] = true;
for(int i=rh[ver];i;i=ne[i])
{
int j = e[i];
if(dist[j]>dist[ver]+w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j],j});
}
}
}
}
int astar()
{
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
// 谁的d[u]+f[u]更小 谁先出队列
heap.push({dist[S], {0, S}});
while(heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y.y,distance = t.y.x;
cnt[ver]++;
//如果终点已经被访问过k次了 则此时的ver就是终点T 返回答案
if(cnt[T]==K) return distance;
for(int i=h[ver];i!=-1;i=ne[i])
{
int j = e[i];
/*
如果走到一个中间点都cnt[j]>=K，则说明j已经出队k次了，且astar()并没有return distance,
说明从j出发找不到第k短路(让终点出队k次)，
即继续让j入队的话依然无解，
那么就没必要让j继续入队了
*/
if(cnt[j] < K)
{
// 按 真实值+估计值 = d[j]+f[j] = dist[S->t] + w[t->j] + dist[j->T] 堆排
// 真实值 dist[S->t] = distance+w[i]
heap.push({distance+w[i]+dist[j],{distance+w[i],j}});
}
}
}
// 终点没有被访问k次
return -1;
}
int main()
{
cin >> m >> n;
for(int i=0;i<n;i++)
{
int a,b,c;
cin >> a >> b >> c;
add(h,a,b,c);
add(rh,b,a,c);
}
cin >> S >> T >> K;
// 起点==终点时 则d[S→S] = 0 这种情况就要舍去 ,总共第K大变为总共第K+1大
if (S == T) K ++ ;
// 从各点到终点的最短路距离 作为估计函数f[u]
dijkstra();
cout << astar();
return 0;
}
分层图
问题引入：给你n个点，m条边，每条边都有边权。现在你可以任意选择k条边，使它的边权为0，问从起点到终点的最短路
1.建k层图，类似于种类并查集
2.开dist[n][k]，用动态规划来求解
先来看下第一种方法
[P4568 [JLOI2011] 飞行路线]([P4568 JLOI2011] 飞行路线 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))
1.建图
图建好后，剩下的就是正常的跑最短路了。但是，有一点需要注意：不见得最优答案会产生在第k层图中。也就是，不见得会跑到第k层图中。
什么时候会出现这种情况呢？当m < k m < km<k的时候。假设m = 1 , k = 10 m = 1, k = 10m=1,k=10，我们只有一条边，也就是说，我们最多建两层图。那么遇到这种情况该怎么办呢？
1.可以在每一层的终点处向下一层的终点处连一条边
2.可以在统计答案的时候在每一层中取最小值
两种方法任取其一
for (int i = 1; i <= m; i++) {//总共k+1层图
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
add(y, x, z);
for (int j = 1; j <= k; j++) {
add(x + j * n, y + j * n);
add(y + j * n, x + j * n);
add(x + (j - 1) * n, y + j * n);
add(y + (j - 1) * n, x + j * n);
}
}
dijkstra();
int ans = 0x7f7f7f7f;
for(int i = 0; i <= k; i ++) ans = min(ans, dis[t + i * n]);//统计每一层的答案,k+1层
printf("%d", ans);
最小生成树
1.prime（朴素版）
void prim() {
memset(dist, 0x3f, sizeof dist);
int res = 0;
dist[1] = 0;
for (int i = 1; i <= n; i++) {
int t = -1;
for (int j = 1; j <= n; j++)
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
if (dist[t] == INF) {
cout << "no answer" << endl;
return;
}
res += dist[t];
st[t] = true;
for (int j = 1; j <= n; j++) dist[j] = min(dist[j], g[t][j]);
}
cout << res << endl;
}
2.kruskal
int n, m; // n是点数，m是边数
int p[N]; // 并查集的父节点数组
struct Edge // 存储边
{
int a, b, w;
bool operator< (const Edge &W)const
{
return w < W.w;
}
}edges[M];
int find(int x) // 并查集核心操作
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int 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) // 如果两个连通块不连通，则将这两个连通块合并
{
p[a] = b;
res += w;
cnt ++ ;
}
}
if (cnt < n - 1) return INF;
return res;
}
3.次小生成树（倍增）
复杂度
$O(mlogm)$
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, M = 300010, INF = 0x3f3f3f3f;
int n, m;
struct Edge
{
int a, b, w;
bool used;
bool operator< (const Edge &t) const
{
return w < t.w;
}
}edge[M];
int p[N];
int h[N], e[M], w[M], ne[M], idx;
int depth[N], fa[N][17], d1[N][17], d2[N][17];
int q[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
LL kruskal()
{
for (int i = 1; i <= n; i ++ ) p[i] = i;
sort(edge, edge + m);
LL res = 0;
for (int i = 0; i < m; i ++ )
{
int a = find(edge[i].a), b = find(edge[i].b), w = edge[i].w;
if (a != b)
{
p[a] = b;
res += w;
edge[i].used = true;
}
}
return res;
}
void build()
{
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
if (edge[i].used)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
add(a, b, w), add(b, a, w);
}
}
void bfs()
{
memset(depth, 0x3f, sizeof depth);
depth[0] = 0, depth[1] = 1;
q[0] = 1;
int hh = 0, tt = 0;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; ~i; i = ne[i])
{
int j = e[i];
if (depth[j] > depth[t] + 1)
{
depth[j] = depth[t] + 1;
q[ ++ tt] = j;
fa[j][0] = t;
d1[j][0] = w[i], d2[j][0] = -INF;
for (int k = 1; k <= 16; k ++ )
{
int anc = fa[j][k - 1];
fa[j][k] = fa[anc][k - 1];
int distance[4] = {d1[j][k - 1], d2[j][k - 1], d1[anc][k - 1], d2[anc][k - 1]};
d1[j][k] = d2[j][k] = -INF;
for (int u = 0; u < 4; u ++ )
{
int d = distance[u];
if (d > d1[j][k]) d2[j][k] = d1[j][k], d1[j][k] = d;
else if (d != d1[j][k] && d > d2[j][k]) d2[j][k] = d;
}
}
}
}
}
}
int lca(int a, int b, int w)
{
static int distance[N * 2];
int cnt = 0;
if (depth[a] < depth[b]) swap(a, b);
for (int k = 16; k >= 0; k -- )
if (depth[fa[a][k]] >= depth[b])
{
distance[cnt ++ ] = d1[a][k];
distance[cnt ++ ] = d2[a][k];
a = fa[a][k];
}
if (a != b)
{
for (int k = 16; k >= 0; k -- )
if (fa[a][k] != fa[b][k])
{
distance[cnt ++ ] = d1[a][k];
distance[cnt ++ ] = d2[a][k];
distance[cnt ++ ] = d1[b][k];
distance[cnt ++ ] = d2[b][k];
a = fa[a][k], b = fa[b][k];
}
distance[cnt ++ ] = d1[a][0];
distance[cnt ++ ] = d1[b][0];
}
int dist1 = -INF, dist2 = -INF;
for (int i = 0; i < cnt; i ++ )
{
int d = distance[i];
if (d > dist1) dist2 = dist1, dist1 = d;
else if (d != dist1 && d > dist2) dist2 = d;
}
if (w > dist1) return w - dist1;
if (w > dist2) return w - dist2;
return INF;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < m; i ++ )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
edge[i] = {a, b, c};
}
LL sum = kruskal();
build();
bfs();
LL res = 1e18;
for (int i = 0; i < m; i ++ )
if (!edge[i].used)
{
int a = edge[i].a, b = edge[i].b, w = edge[i].w;
res = min(res, sum + lca(a, b, w));
}
printf("%lld\n", res);
return 0;
}
最近公共祖先（lca）
1.朴素算法
过程
可以每次找深度比较大的那个点，让它向上跳。显然在树上，这两个点最后一定会相遇，相遇的位置就是想要求的 LCA。 或者先向上调整深度较大的点，令他们深度相同，然后再共同向上跳转，最后也一定会相遇。
性质
朴素算法预处理时需要 dfs 整棵树，时间复杂度为$O(n)$，单次查询时间复杂度为 $O(n)$
。如果树满足随机性质，则时间复杂度与这种随机树的期望高度有关。
2.倍增算法
复杂度
预处理$O(nlogn)$，查询$O(logn)$
代码
//bfs求
int depth[N], fa[N][16];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void bfs(int root) {
memset(depth, 0x3f, sizeof depth);//初始化为INF是为了防止节点重复遍历
depth[0] = 0, depth[root] = 1;//depth[0]=0充当哨兵
queue<int> q;
q.push(root);
while (q.size()) {
int t = q.front();
q.pop();
for (int i = h[t]; i; i = ne[i]) {
int j = e[i];
if (depth[j] > depth[t] + 1) {
depth[j] = depth[t] + 1;
q.push(j);
fa[j][0] = t;
for (int k = 1; k <= 15; k++)
fa[j][k] = fa[fa[j][k - 1]][k - 1];
}
}
}
}
int lca(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
for (int k = 15; k >= 0; k--)
if (depth[fa[a][k]] >= depth[b])
a = fa[a][k];
if (a == b) return a;
for (int k = 15; k >= 0; k--)
if (fa[a][k] != fa[b][k]) {
a = fa[a][k];
b = fa[b][k];
}
return fa[a][0];
}
//dfs求
void dfs(int u, int father){
dep[u] = dep[father] + 1;
fa[u][0] = father;
for(int i = 1; (1 << i) <= dep[u]; ++i)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(auto v : g[u])
if(v ^ father)
dfs(v, u);
}
int lca(int u, int v){
if(dep[u] < dep[v]) std::swap(u, v);
for(int i = 19; i >= 0; --i)
if(dep[u] - (1 << i) >= dep[v])
u = fa[u][i];
if(u == v) return v;
for(int i = 19; i >= 0; --i)
if(fa[u][i] != fa[v][i]){
u = fa[u][i];
v = fa[v][i];
}
return fa[u][0];
}
3.应用
连通性相关
强联通分量
简介
强连通的定义是：有向图 G 强连通是指，G 中任意两个结点连通。
强连通分量（Strongly Connected Components，SCC）的定义是：极大的强连通子图。
这里要介绍的是如何来求强连通分量。
targan算法
时间复杂度
$O(n)$
代码
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stk[++top] = u, in_stk[u] = true;
for (int i = h[u]; i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u]) {
int y;
scc_cnt++;
do {
y = stk[top--];
in_stk[y] = false;
id[y] = scc_cnt;
siz[scc_cnt]++;
} while (y != u);
}
}
缩点
我们可以将一张图的每个强连通分量都缩成一个点。
然后这张图会变成一个 DAG，可以进行拓扑排序以及更多其他操作。
对于缩点，缩点后可以构建一张DAG，可以用拓扑排序来得到拓扑序，但这里有一种更简单的方法
根据targan算法的性质，以scc_cnt的降序顺序进行遍历即为拓扑序
set<ll> hask; //哈希函数可以为 a*1000000+b,因为a最大为1e5，这样保证不同的a,b，哈希值不同
for (int i = 1; i <= n; i++)
for (int j = h[i]; j; j = ne[j]) {
int k = e[j];
int a = id[i], b = id[k];
ll h = a * 1000000ll + b; //a乘与的数根据实际题目范围来定
if (a != b && !hask.count(h)) {//如果二者不在同一个强联通分量且边没被加过
hask.insert(h);
add(fh, a, b);
}
}
for (int i = scc_cnt; i; i--) { //不用再做一遍拓扑排序，按scc_cnt的降序遍历就是拓扑排序
//填入操作
}
最大半联通子图
[最大半联通子图](AcWing 1175. 最大半连通子图 - AcWing)
问题分析
- 问题引入：将一个有向图补全为强联通图，至少需要增加几条边？
答案及证明如下：
代码
#include<iostream>
#include<set>
#include<cstring>
using namespace std;
const int N = 1e5 + 10, M = 2e6 + 10;
using ll = long long;
int n, m;
int mod;
int h[N], fh[N], e[M], ne[M], idx = 1;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool in_stk[N];
int scc_cnt, id[N];
int d[N], ans[N];
int siz[N];
inline void add(int h[], int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u) {
dfn[u] = low[u] = ++timestamp;
stk[++top] = u, in_stk[u] = true;
for (int i = h[u]; i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j);
low[u] = min(low[u], low[j]);
}
else if (in_stk[j]) low[u] = min(low[u], dfn[j]);
}
if (low[u] == dfn[u]) {
int y;
scc_cnt++;
do {
y = stk[top--];
id[y] = scc_cnt;
in_stk[y] = false;
siz[scc_cnt]++;
} while (y != u);
}
}
int main() {
cin >> n >> m >> mod;
for (int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
add(h, a, b);
}
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
set<ll> hask; //哈希函数可以为 a*1000000+b,因为a最大为1e5，这样保证不同的a,b，哈希值不同
for (int i = 1; i <= n; i++)
for (int j = h[i]; j; j = ne[j]) {
int k = e[j];
int a = id[i], b = id[k];
ll h = a * 1000000ll + b;
if (a != b && !hask.count(h)) {//如果二者不在同一个强联通分量且边没被加过
hask.insert(h);
add(fh, a, b);
}
}
for (int i = scc_cnt; i; i--) { //不用再做一遍拓扑排序，按scc_cnt的降序遍历就是拓扑排序
if (!d[i]) {
d[i] = siz[i], ans[i] = 1;//初始化
}
for (int j = fh[i]; j; j = ne[j]) {
int k = e[j];
if (d[k] < d[i] + siz[k]) {
d[k] = d[i] + siz[k];
ans[k] = ans[i];
}
else if (d[k] == d[i] + siz[k])
ans[k] = (ans[k] + ans[i]) % mod;
}
}
int maxn = 0, sum = 0;
for(int i=1;i<=scc_cnt;i++)
if (d[i] > maxn) {
maxn = d[i];
sum = ans[i];
}
else if (d[i] == maxn)
sum = (sum + ans[i]) % mod;
cout << maxn << endl << sum << endl;
return 0;
}
双联通分量
前置概念
桥：对于一个无向图，如果删掉一条边后图中的连通分量数增加了，则称这条边为桥或者割边
割点：对于一个无向图，如果把一个点删除后这个图的极大连通分量数增加了，那么这个点就是这个图的割点（又称割顶）
点联通分量，边联通分量（二者不存在包含关系）
一些概念性质简单介绍：割点 桥 点/边双连通分量（BCC） - tom0727's blog
边联通分量
解法
targin 算法，与强联通分量相似，当$dfn[u]<low[j]$，u，j之间的边就是桥
当dfn[u]==low[u]时，得到新的变联通分量
代码
//idx初始要为零
void tarjan(int u, int from) { //from代表刚遍历过的边
dfn[u] = low[u] = ++timestamp;
stk[++top] = u;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j, i);
low[u] = min(low[u], low[j]);
if (dfn[u] < low[j]) //说明u和j之间的边为桥
is_bridge[i] = is_bridge[i ^ 1] = true; //这条边的正边反边都是桥，因为按i^1这样写，所以idx初始要为0
}
else if (i != (from ^ 1))//如果不走走过的边的反边，也就是重复走
low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u]) {
int y;
dcc_cnt++;
do {
y = stk[top--];
id[y] = dcc_cnt;
} while (y != u);
}
}
//vector存图的写法
auto tarjan = [&](auto&& self, int u) -> void {
root[u] = dfn[u] = ++timestamp;
for (auto y : g[u]) {
if (!dfn[y]) {
fa[y] = u;
self(self, y);
root[u] = min(root[u], root[y]);
if (root[y] > dfn[u])
cut_edge.insert({u, y});
} else if (y != fa[u])
root[u] = min(root[u], dfn[y]);
}
};
例题
[acwing \395. 冗余路径](395. 冗余路径 - AcWing题库)
分析：要使任意两点之间都有两条即两条以上不相关的路劲，这显然符合边联通分量的性质，说明可以用tanjan缩点，缩点后的图就是 一颗树，树中的边则是原图中的桥，若使这棵树边联通，该树度数为1的节点个数为cnt，答案即为$(cnt+1)/2$
重点
- 缩点后的图就是一颗树，树中的边则是原图中的桥
- 若使这棵树边联通，该树度数为1的节点个数为cnt，答案即为$(cnt+1)/2$
结题步骤
- 缩点
- 求缩点后度数为一的点的数目
代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5010, M = 20010;
int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
int id[N], dcc_cnt;
bool is_bridge[M];
int d[N];//边联通分量的度数
inline void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void tarjan(int u, int from) { //from代表刚遍历过的边
dfn[u] = low[u] = ++timestamp;
stk[++top] = u;
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!dfn[j]) {
tarjan(j, i);
low[u] = min(low[u], low[j]);
if (dfn[u] < low[j]) //说明u和j之间的边为桥
is_bridge[i] = is_bridge[i ^ 1] = true; //这条边的正边反边都是桥，因为按i^1这样写，所以idx初始要为0
}
else if (i != (from ^ 1))//如果不走走过的边的反边，也就是重复走
low[u] = min(low[u], dfn[j]);
}
if (dfn[u] == low[u]) {
int y;
dcc_cnt++;
do {
y = stk[top--];
id[y] = dcc_cnt;
} while (y != u);
}
}
int main() {
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
tarjan(1, -1);
for (int i = 0; i < idx; i++) //枚举所有的桥，（每个桥一定连着两个边联通分量），统计边联通分量的度
if (is_bridge[i])
d[id[e[i]]]++;
int cnt = 0;
for (int i = 1; i <= dcc_cnt; i++)
if (d[i] == 1)
cnt++;
cout << (cnt + 1) / 2 << endl;
return 0;
}
点联通分量
割点的判断
当$low[y]\leq dfn[x]$时，如下情况时，$x$是割点
- $x$不是根节点
- $x$是根节点，但$x$至少有两个子节点
二分图
匈牙利算法（二分图的最大匹配）
时间复杂度
$O(nm)$
代码
#include<iostream>
#include<cstring>
using namespace std;
const int N = 510, M = 5e4 + 10;
int n, m, t;
int h[N], e[M], ne[M], idx = 1;
int match[N];//代表右边的的点和左边的哪个点匹配，为0则为未匹配
bool st[N];
inline 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; i = ne[i]) {
int j = e[i];
if (!st[j]) {
st[j] = true;
if (!match[j] || find(match[j])) //如果可以匹配
{
match[j] = x;
return true;
}
}
}
return false;
}
int main() {
cin >> n >> m >> t;
while (t--) {
int a, b;
cin >> a >> b;
add(a, b);
}
int res = 0;
for (int i = 1; i <= n; i++)//遍历左边的点，计算最大匹配数
{
memset(st, false, sizeof st);//清空数组st,st是判断当点i进行匹配时，右边的点是否能匹配
if (find(i)) res++;
}
cout << res << endl;
return 0;
}
基础算法
快速排序
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> nums;
void quick_sort(int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1, x = nums[l + r >> 1];
while (i < j) {
do i++; while (nums[i] < x);
do j--; while (nums[j] > x);
if (i < j) swap(nums[i], nums[j]);
}
quick_sort(l, j), quick_sort(j + 1, r);
}
int main() {
cin >> n;
nums.resize(n);
for (int i = 0; i < n; i++) cin >> nums[i];
quick_sort(0, n - 1);
for (auto t : nums) cout << t << " ";
return 0;
}
归并排序
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> nums;
vector<int> p;
void merge_sort(int l, int r) {
if (l >= r) return;
int mid = l + r >> 1, i = l, j = mid + 1;
merge_sort(l, mid), merge_sort(mid + 1, r);
int k = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) p[k++] = nums[i++];
else p[k++] = nums[j++];
}
while (i <= mid) p[k++] = nums[i++];
while (j <= r) p[k++] = nums[j++];
for (int i = l, j = 0; i <= r; i++, j++) nums[i] = p[j];
}
int main() {
cin >> n;
nums.resize(n);
p.resize(n);
for (int i = 0; i < n; i++) cin >> nums[i];
merge_sort(0, n - 1);
for (auto t : nums) cout << t << " ";
return 0;
}
贪心
反悔贪心：【学习笔记】反悔贪心 - Koshkaaa (cnblogs.com)
二分
一种二分模版
int answer=-1;//二分出来的值
while(l<=r){//注意是等于
int mid=l+r>>1;
if(符合条件) {
l=mid+1;
answer=max(l,answer);//因为mid为正确值，所以每次取更优的mid
}else r=mid-1;
}
优点
1.l和r的取值固定，不需要再变化
2.如果一直二分不到正确的值，不用再判断二分得到的值是否正确，answer事先取一个标志值，如果二分不到正确答案，answer即为标志值不变
计算几何
距离
欧式距离
设$A,B$的坐标分别为，$(x_1,y_1),(x_2,y_2)$，则两点之间的欧式距离为
$$|AB|=\sqrt{(x_1-x_2)2+(y_1-y_2)2}$$
杂
取整
1.向下取整：对于正数，c++默认向零取整，即向下取整，或者使用floor()函数
2.向上取整：使用ceil()函数或者,如果对A/B向上取整，可（A+B-1)/B
3.四舍五入： round()函数
关于memset
特性
memset是按字节赋值，一般有以下常用：
- 0，初始化为0
- -1，初始化为-1
- 0x3f，初始化为0x3f3f3f3f，1061109567
- 0x7f，初始化为0x7f7f7f7f，2139062143
- -0x3f，初始化为-1044266559
注意：0x7fffffff是int中的最大值，为2147483647
卡常
#