标签：std 数据结构 return int tr ++ include CSP 模板

CSP-S 算法总结

2.2.1 基础知识与编程环境

无
2.2.2 C++ 程序设计 2
- set/nultiset
- map/multimap
- deque/priority_queue
- STL

2.2.3 数据结构

P1886 滑动窗口 /【模板】单调队列

#include <iostream>
using namespace std;

int n, k, a[1000005];
int q[1000005], h, t;

void maxx() {
    h = 0; t = -1;
    for (int i = 1; i <= n; ++i) {
        while (h <= t && a[q[t]] <= a[i]) t--;
        q[++t] = i;
        if (q[h] <= i - k) h++;
        if (i >= k) cout << a[q[h]] << " ";
    }
    cout << endl;
}

void minn() {
    h = 0; t = -1;
    for (int i = 1; i <= n; ++i) {
        while (h <= t && a[q[t]] >= a[i]) t--;
        q[++t] = i;
        if (q[h] <= i - k) h++;
        if (i >= k) cout << a[q[h]] << " ";
    }
    cout << endl;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    minn();
    maxx();
    return 0;
}

P3865 【模板】ST 表

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int Max[MAXN][21];

int Query(int l, int r) {
    int k = log2(r - l + 1);
    return max(Max[l][k], Max[r - (1 << k) + 1][k]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
        cin >> Max[i][0];
    
    for (int j = 1; j <= 21; j++)
        for (int i = 1; i + (1 << (j - 1)) <= N; i++)
            Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);

    for (int i = 1; i <= M; i++) {
        int l, r;
        cin >> l >> r;
        cout << Query(l, r) << '\n';
    }
    return 0;
}

P3367 【模板】并查集

#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,s,ans,f[10010],p1,p2,p3;
//f[i]表示i的集合名
int find(int k){
  //路径压缩
    if(f[k]==k)return k;
    return f[k]=find(f[k]);
}
int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
        f[i]=i;//初始化i的老大为自己
    for(i=1;i<=m;i++){
        cin>>p1>>p2>>p3;
        if(p1==1)
            f[find(p2)]=find(p3);
            //p3打赢了p2
        else
            if(find(p2)==find(p3))
            //是否是一伙的
                printf("Y\n");
            else
                printf("N\n");
    }
    return 0;
}

P3374【模板】树状数组 1

#include <bits/stdc++.h> 
using namespace std;
int n,m,tree[2000010];
int lowbit(int k) { return k & -k; }
void add(int x,int k) {
  while(x<=n) {
    tree[x]+=k;
    x+=lowbit(x);
  }
}
int sum(int x) {
  int ans=0;
  while(x!=0) {
    ans+=tree[x];
    x-=lowbit(x);
  }
  return ans;
}
int main() {
  cin>>n>>m;
  for(int i=1; i<=n; i++) {
    int a;
    cin>>a;
    add(i,a);
  }
  for(int i=1; i<=m; i++) {
    int a,b,c;
    cin>>a>>b>>c;
    if(a==1)
      add(b,c);
    if(a==2)
      cout<<sum(c)-sum(b-1)<<endl;
  }
}

P3372 【模板】线段树 1

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 1000005
ll a[maxn],w[maxn*4],lzy[maxn*4];

void pushup(int u){w[u]=w[u*2]+w[u*2+1];}   

void build(int u,int L,int R){       //线段树建立
  if(L==R){w[u]=a[L];return;}
  int M=L+R>>1;
  build(u*2,L,M);
  build(u*2+1,M+1,R);
  pushup(u);
}

ll query1(int u,int L,int R,int p){   //单点查询
  if(L==R) return w[u];
  else {
    int M=L+R>>1;
    if(M>=p) return query1(u*2,L,M,p);
    else return query1(u*2+1,M+1,R,p);
  }
}

void update1(int u,int L,int R,int p,ll x){    //单点修改
  if(L==R) w[u]=x;
  else{
    int M=L+R>>1;
    if(M>=p)  update1(u*2,L,M,p,x);
    else  update1(u*2+1,M+1,R,p,x);
    pushup(u);
  }
}

bool InRange(int L,int R,int l,int r){return ((l<=L)&&(R<=r));}   //判断 [L,R] 是否被 [l,r] 包含
bool OutoRange(int L,int R,int l,int r){ return ((L>r)||(R<l));}  //判断 [L,R] 是否和 [l,r] 无交

void maketag(int u,int len,int x){
  lzy[u]+=x;
  w[u]+=len*x;
}

void pushdown(int u,int L,int R){
  int M=L+R>>1;
  maketag(u*2,M-L+1,lzy[u]);
  maketag(u*2+1,R-M,lzy[u]);
  lzy[u]=0;
}
ll query(int u,int L,int R,int l,int r){
  if(InRange(L,R,l,r)){return w[u];}
  else if(!OutoRange(L,R,l,r)){
    int M=L+R>>1;
    pushdown(u,L,R);
    return query(u*2,L,M,l,r)+query(u*2+1,M+1,R,l,r);
  }
  else return 0;
}



void update(int u,int L,int R,int l,int r,ll x){
  if(InRange(L,R,l,r)){maketag(u,R-L+1,x);}

  else if(!OutoRange(L,R,l,r)){
    int M=L+R>>1;
    pushdown(u,L,R);
    update(u*2,L,M,l,r,x);
    update(u*2+1,M+1,R,l,r,x);
    pushup(u);
  }
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
  
  int n,m;
  cin>>n>>m;
  for(int i=1;i<=n;i++){cin>>a[i];}
  build(1,1,n);
  for(int i=1;i<=m;i++){
    int op,x,y;
    cin>>op;
    ll k;
    if(op==1){
      cin>>x>>y>>k;
      update(1,1,n,x,y,k);
    }
    else{
      cin>>x>>y;
      cout<<query(1,1,n,x,y)<<endl;
    }
  }
  return 0;
}

P8306 【模板】字典树

#include<bits/stdc++.h>
using namespace std;
int T,q,n,t[3000005][65],cnt[3000005],idx;
char s[3000005];
int getnum(char x){
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
} 
void insert(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            t[p][c]=++idx;
        p=t[p][c];
        cnt[p]++;
    }
}
int find(char str[]){
    int p=0,len=strlen(str);
    for(int i=0;i<len;i++){
        int c=getnum(str[i]);
        if(!t[p][c])
            return 0;
        p=t[p][c];
    }
    return cnt[p];
}
int main(){
    scanf("%d",&T);
    while(T--){
        for(int i=0;i<=idx;i++)
            for(int j=0;j<=122;j++)
                t[i][j]=0;
        for(int i=0;i<=idx;i++)
            cnt[i]=0;
        idx=0;
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%s",s);
            insert(s);
        }
        for(int i=1;i<=q;i++){
            scanf("%s",s);
            printf("%d\n",find(s));
        }
    }
    return 0;
}

P3369 【模板】普通平衡树

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

using namespace std;

const int N = 100010, INF = 1e8;

int n;
struct Node
{
    int l, r;
    int key, val;
    int cnt, size;
}tr[N];

int root, idx;

void pushup(int p)
{
    tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
}

int get_node(int key)
{
    tr[ ++ idx].key = key;
    tr[idx].val = rand();
    tr[idx].cnt = tr[idx].size = 1;
    return idx;
}

void zig(int &p)    // 右旋
{
    int q = tr[p].l;
    tr[p].l = tr[q].r, tr[q].r = p, p = q;
    pushup(tr[p].r), pushup(p);
}

void zag(int &p)    // 左旋
{
    int q = tr[p].r;
    tr[p].r = tr[q].l, tr[q].l = p, p = q;
    pushup(tr[p].l), pushup(p);
}

void build()
{
    get_node(-INF), get_node(INF);
    root = 1, tr[1].r = 2;
    pushup(root);

    if (tr[1].val < tr[2].val) zag(root);
}


void insert(int &p, int key)
{
    if (!p) p = get_node(key);
    else if (tr[p].key == key) tr[p].cnt ++ ;
    else if (tr[p].key > key)
    {
        insert(tr[p].l, key);
        if (tr[tr[p].l].val > tr[p].val) zig(p);
    }
    else
    {
        insert(tr[p].r, key);
        if (tr[tr[p].r].val > tr[p].val) zag(p);
    }
    pushup(p);
}

void remove(int &p, int key)
{
    if (!p) return;
    if (tr[p].key == key)
    {
        if (tr[p].cnt > 1) tr[p].cnt -- ;
        else if (tr[p].l || tr[p].r)
        {
            if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val)
            {
                zig(p);
                remove(tr[p].r, key);
            }
            else
            {
                zag(p);
                remove(tr[p].l, key);
            }
        }
        else p = 0;
    }
    else if (tr[p].key > key) remove(tr[p].l, key);
    else remove(tr[p].r, key);

    pushup(p);
}

int get_rank_by_key(int p, int key)    // 通过数值找排名
{
    if (!p) return 1;   // 本题中不会发生此情况
    if (tr[p].key == key) return tr[tr[p].l].size + 1;
    if (tr[p].key > key) return get_rank_by_key(tr[p].l, key);
    return tr[tr[p].l].size + tr[p].cnt + get_rank_by_key(tr[p].r, key);
}

int get_key_by_rank(int p, int rank)   // 通过排名找数值
{
    if (!p) return INF;     // 本题中不会发生此情况
    if (tr[tr[p].l].size >= rank) return get_key_by_rank(tr[p].l, rank);
    if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p].key;
    return get_key_by_rank(tr[p].r, rank - tr[tr[p].l].size - tr[p].cnt);
}

int get_prev(int p, int key)   // 找到严格小于key的最大数
{
    if (!p) return -INF;
    if (tr[p].key >= key) return get_prev(tr[p].l, key);
    return max(tr[p].key, get_prev(tr[p].r, key));
}

int get_next(int p, int key)    // 找到严格大于key的最小数
{
    if (!p) return INF;
    if (tr[p].key <= key) return get_next(tr[p].r, key);
    return min(tr[p].key, get_next(tr[p].l, key));
}

int main()
{
    build();

    scanf("%d", &n);
    while (n -- )
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(root, x);
        else if (opt == 2) remove(root, x);
        else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
        else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1 ));
        else if (opt == 5) printf("%d\n", get_prev(root, x));
        else printf("%d\n", get_next(root, x));
    }

    return 0;
}

P3370 【模板】字符串哈希

#include<bits/stdc++.h>
using namespace std;
set<string> a;
int main(){
    string p;
    int n,i;
    cin>>n;
    for(i=0;i<n;i++){
      cin>>p;
      a.insert(p);
  }
  cout<<a.size()<<endl;
  return 0;
}

2.2.4 算法

离散化

// arr[i] 为初始数组,下标范围为 [1, n]
for (int i = 1; i <= n; ++i)  // step 1
  tmp[i] = arr[i];
std::sort(tmp + 1, tmp + n + 1);                          // step 2
int len = std::unique(tmp + 1, tmp + n + 1) - (tmp + 1);  // step 3
for (int i = 1; i <= n; ++i)                              // step 4
  arr[i] = std::lower_bound(tmp + 1, tmp + len + 1, arr[i]) - tmp;




// std::vector<int> arr;
std::vector<int> tmp(arr);  // tmp 是 arr 的一个副本
std::sort(tmp.begin(), tmp.end());
tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
for (int i = 0; i < n; ++i)
  arr[i] = std::lower_bound(tmp.begin(), tmp.end(), arr[i]) - tmp.begin();

分治

基数排序

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, a[N], tot;
pair<int, int> p[N];
vector<pair<int, int>> G[N];
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++){
      cin >> a[i];
        p[i].first = a[i] >> 16,p[i].second = a[i] % 65536;
  }
    for (int i = 1; i <= n; i++)
        G[p[i].second].push_back(p[i]);
    for (int i = 0; i < 65536; i++)
        for (int j = 0; j < G[i].size(); j++)
            p[++tot] = G[i][j];
    for (int i = 0; i < 65536; i++)
        G[i].clear();
    for (int i = 1; i <= n; i++)
        G[p[i].first].push_back(p[i]);
    tot = 0;
    for (int i = 0; i < 65536; i++)
        for (int j = 0; j < G[i].size(); j++)
            p[++tot] = G[i][j];
    for (int i = 1; i <= n; i++)cout <<( (p[i].first << 16) | p[i].second )<< " ";
    return 0;
}

归并排序

#include <iostream>
using namespace std;
const int N=1e6+10;
int q[N],tmp[N],n;
void MergeSort(int q[],int l,int r){
  if(l>=r) return ;
  int mid=(r+l)>>1;
  MergeSort(q,l,mid);MergeSort(q,mid+1,r);
  int i=l,j=mid+1,k=0;
  while(i<=mid&&j<=r){
    if(q[i]<=q[j]) tmp[k++]=q[i++];
    else tmp[k++]=q[j++];
  }
  while(i<=mid) tmp[k++]=q[i++];
  while(j<=r) tmp[k++]=q[j++];
  for(int i=l,j=0;i<=r;i++) q[i]=tmp[j++];
}
int main(){
  cin>>n;
  for(int i=0;i<n;i++) cin>>q[i];
  MergeSort(q,0,n-1);
  for(int i=0;i<n;i++) cout<<q[i]<<" "; 
  return 0;
}

P3375 【模板】KMP

#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int kmp[MAXN];
int la,lb,j;
char a[MAXN],b[MAXN];
int main() {
  cin>>a+1;
  cin>>b+1;
  la=strlen(a+1);
  lb=strlen(b+1);
  for (int i=2; i<=lb; i++) {
    while(j&&b[i]!=b[j+1])
      j=kmp[j];
    if(b[j+1]==b[i])j++;
    kmp[i]=j;
  }
  j=0;
  for(int i=1; i<=la; i++) {
    while(j>0&&b[j+1]!=a[i])
      j=kmp[j];
    if (b[j+1]==a[i])
      j++;
    if (j==lb) {
      cout<<i-lb+1<<endl;
      j=kmp[j];
    }
  }
  for (int i=1; i<=lb; i++)
    cout<<kmp[i]<<" ";
  return 0;
}

搜索

二分图的判定：

int edge[maxn][maxn];//邻接矩阵存储
int color[maxn];//标记顶点颜色
int n,m;
bool dfs(int u,int c)
{
    color[u]=c;//对u点进行染色
    for(int i=1;i<=n;i++)//遍历与u点相连的点
    {
        if(edge[u][i]==1)//如果i点与u点相连
        {
            if(color[i]==c) return false;//i点的染色重复，则不是二分图
            if(!color[i]&&!dfs(i,-c)) return false;//该点未染色，染上相反的颜色.dfs继续搜索
        }
    }
    return true;//所有点染色完成之后，并且相邻顶点没有同色，则为二分图
}

P3386 【模板】二分图最大匹配

#include <bits/stdc++.h> 
using namespace std;

const int N=1005;
struct edge{
  int to,nxt; 
}e[200010];
int head[N],cnt,n,m,match[N],T;
bool vis[N];
void add(int x,int y){
  e[++cnt]={y,head[x]};
  head[x]=cnt; 
}
bool dfs(int x){
  for(int i=head[x];i;i=e[i].nxt){
    int r=e[i].to;
    if(vis[r]) continue;
    vis[r]=true;
    if(match[r]==0||dfs(match[r])){
      match[r]=x;
      return true;
    }
  }
  return false;
}
int main(){
  cin>>n>>m>>T;
  while(T--){
    int u,v;
    cin>>u>>v;
    add(u,v+n);
    add(v+n,u); 
  } 
  int ans=0;
  for(int i=1;i<=n;i++){
    memset(vis,false,sizeof(vis));
    if(dfs(i)) ans++; 
  }
  cout<<ans<<endl;
  return 0;
}

P7771 【模板】欧拉路径

#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,d[100005],du[100005][2];
stack<int> st;
vector<int> G[100005];
void dfs(int now){
  for(int i=d[now];i<G[now].size();i=d[now]){ 
    d[now]=i+1;
    dfs(G[now][i]);
  }
  st.push(now);
}

int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>u>>v;
    G[u].push_back(v);
    du[u][1]++;
    du[v][0]++; 
  }
  for(int i=1;i<=n;i++){
    sort(G[i].begin(),G[i].end());
  }
  int S=1,cnt[2]={0,0};
  bool flag=1;
  for(int i=1;i<=n;i++){
    if(du[i][1]!=du[i][0]){
      flag=0;
      if(du[i][1]-du[i][0]==1) cnt[1]++,S=i;
            else if(du[i][0]-du[i][1]==1) cnt[0]++;
            else return puts("No"),0;
    } 
  }
  if(!flag&&!(cnt[0]==cnt[1]&&cnt[0]==1)) return puts("No"),0;
  dfs(S);
  while(!st.empty()) printf("%d ",st.top()),st.pop();
  return 0;
}

P8436【模板】边双连通分量

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int N = 500010, M = 2000010 * 2;

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 tot[N];
vector <int> ans[N];

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

void tarjan(int u, int 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 (low[j] > dfn[u])
        is_bridge[i] = is_bridge[i ^ 1] = true;
    }
    else if (i != (1 ^ from))
      low[u] = min(low[u], dfn[j]);
  }
  
  if (dfn[u] == low[u])
  {
    dcc_cnt ++ ;
    int y;
    do
    {
      y = stk[top -- ];
      id[y] = dcc_cnt;
    } while (y != u);
  }
  
  return;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  memset(h, -1, sizeof h);
  for (int i = 1; i <= m; i ++ )
  {
    int a, b;
    cin >> a >> b;
    add(a, b);
    add(b, a);
  }
  
  for (int i = 1; i <= n; i ++ )
    if (!dfn[i]) tarjan(i, -1);
  
  cout << dcc_cnt << endl;
  
  for (int i = 1; i <= n; i ++ )
  {
    tot[id[i]] ++ ;
    ans[id[i]].push_back(i);
  }
  
  int p = 1;
  while (tot[p])
  {
    cout << tot[p] << ' ';
    for (int i = 0; i < ans[p].size(); i ++ )
      cout << ans[p][i] << ' ';
    p ++ ;
    cout << endl;
  }
  
  return 0;
}

P8435【模板】点双连通分量

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5, M = 4e6 + 5;
int cnt = 1, fir[N], nxt[M], to[M];
int s[M], top, bcc, low[N], dfn[N], idx, n, m;
vector<int> ans[N];
inline void tarjan(int u, int fa) {
  int son = 0;
  low[u] = dfn[u] = ++idx;
  s[++top] = u;
  for(int i = fir[u]; i; i = nxt[i]) {
    int v = to[i];
    if(!dfn[v]) {
      son++;
      tarjan(v, u);
      low[u] = min(low[u], low[v]);
      if(low[v] >= dfn[u]) {
        bcc++;
        while(s[top + 1] != v) ans[bcc].push_back(s[top--]);//将子树出栈
        ans[bcc].push_back(u);//把割点/树根也丢到点双里
      }
    } else if(v != fa) low[u] = min(low[u], dfn[v]);
  }
  if(fa == 0 && son == 0) ans[++bcc].push_back(u);//特判独立点
}
inline void add(int u, int v) {
  to[++cnt] = v;
  nxt[cnt] = fir[u];
  fir[u] = cnt;
}
int main() {
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    add(u, v), add(v, u);
  }
  for(int i = 1; i <= n; i++) {
    if(dfn[i]) continue;
    top = 0;
    tarjan(i, 0);
  }
  printf("%d\n", bcc);
  for(int i = 1; i <= bcc; i++) {
    printf("%d ", ans[i].size());
    for(int j : ans[i]) printf("%d ", j);
    printf("\n");
  }
  return 0;
}

DAG拓扑排序：

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 100;
const int M = 4e5 + 100;
int head[N], Next[M], ver[M], tot;
int deg[N];
void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}
queue<int>qc;
int topsort(int n) {
    int cnt = 0;
    while (qc.size())
        qc.pop();
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            qc.push(i);
        }
    }
    while (qc.size()) {
        int x = qc.front();
        cnt++;
        qc.pop();
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i];
            if (--deg[y] == 0)
                qc.push(y);
        }
    }
    return cnt == n;
}
int main() {
    int n, m, x, y;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        add(x, y);
        deg[y]++;
    }
    if (topsort(n))
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;
}

Dijkstra \(O((n+m)\times log(n+m))\)

#include <bits/stdc++.h>
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define ROF(i,a,b) for(int i=(a);i>=(b);--i)
#define U unsigned
#define LL long long
using namespace std;
template<class T>
inline void read(T &a){ register U LL x=0,t=1; register char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') t=-1; ch=getchar();} while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } a=x*t;}
inline void print(LL x){if(x<0)putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0');}
int n,m,s;
vector<pair<int,int> > v[200005];
int dis[200005];
struct node{
  int d,id;
  bool friend operator < (node xx,node yy){
    return xx.d>yy.d;
  }
};
priority_queue<node>Q;    
void dij(){
  for(int i=1;i<=n;i++) dis[i]=2e9;
  dis[s]=0;
  Q.push({0,s});
  while(!Q.empty()){
    int d=Q.top().d; 
    int id=Q.top().id;
    Q.pop();
    if(d>dis[id]) continue;
    for(int i=0;i<v[id].size();i++){
      int to=v[id][i].first;
      if(dis[to]>dis[id]+v[id][i].second){
        dis[to]=dis[id]+v[id][i].second;
        Q.push({dis[to],to});
      }
    }
  }
}
void sovle(){
  cin>>n>>m>>s;
  for(int i=1;i<=m;i++){
    int x,y,c;
    cin>>x>>y>>c;
    v[x].push_back({y,c});
  }
  dij();
  for(int i=1;i<=n;i++){
    cout<<dis[i]<<" ";
  } 
}
signed main(){
    sovle();
  return 0;
}

SPFA：

#include<bits/stdc++.h>
#define inf 1000000000
#define N 200020
using namespace std;
queue<int>Q;
int dis[N];
bool vis[N];
int n, m, s;
int head[N], pos;
struct edge { int to, next, c; }e[N];
void add(int a, int b, int c) {
    pos++; e[pos].to = b, e[pos].c = c, e[pos].next = head[a], head[a] = pos;
}
void spfa() {
    for (int i = 1; i <= n; i++)
        dis[i] = inf, vis[i] = 0;
    dis[s] = 0, vis[s] = 1, Q.push(s);
    while (!Q.empty())
    {
        int u = Q.front(); Q.pop(); vis[u] = 0;
        for (int i = head[u]; i; i = e[i].next)
        {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].c) {
                dis[v] = dis[u] + e[i].c;
                if (!vis[v])vis[v] = 1, Q.push(v);
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        add(x, y, c);
        add(y, x, c);
    }
    spfa();
}

Floyd:

for (k = 1; k <= n; k++)
  for (x = 1; x <= n; x++)
    for (y = 1; y <= n; y++)
      f[x][y] = min(f[x][y], f[x][k] + f[k][y]);

Bellman-Ford:

int dis[maxv][maxv];        //dis[k][v];表示选取前k个时到达i的最短距离
struct Edge
{
    int u, v, w;
}edge[maxv];
int n, m;

void Bellman_Ford(int s)
{
    memset(dis, INF, sizeof(dis));
    for (int i = 1; i <= n; i++)  dis[i][s] = 0;
    for (int k = 1; k <= n - 1; k++)            
        for (int i = 0; i < m; i++)                
        {
            int u = edge[i].u, v = edge[i].v, w = edge[i].w;
            dis[k][v] = min(dis[k][v], dis[k - 1][u] + w);
        }
}

Kosaraju:

#include<bits/stdc++.h>
#define N 200020
using namespace std;
int n, m;
int head[N], pos;
struct edge { to, next, c; }e[N << 1];
void add(int a, int b, int c)
{
    pos++; e[pos].to = b, e[pos].next = head[a], head[a] = pos; e[pos].c = c;
}
int tot, scc;
int st[N], top;
bool vis[N];
void dfs1(int u)
{
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (vis[v] || e[i].c == 0)continue;
        dfs1(v);
    }
    st[++top] = u;
}
int bel[N];
void dfs2(int u, int bl)
{
    bel[u] = bl, vis[u] = 1;
    for (int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if (vis[v] || e[i].c)continue;
        dfs2(v, bl);
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y, 1), add(y, x, 0);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])dfs1(i);
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    for (int i = top; i; i--)
        if (!vis[st[i]]) {
            ++scc;
            dfs2(st[i], scc);
        }
    cout << scc << endl; //scc是强连通分量的数量
}

Tarjan(强连通分量):

#include<bits/stdc++.h>
using namespace std;

int n,m,cnt,cntb;
vector<int> edge[10001];
vector<int> belong[10001];
bool instack[10001];
int dfn[10001];
int low[10001];
stack<int> s;
void Tarjan(int u){
  ++cnt;
  dfn[u]=low[u]=cnt;
  s.push(u);
  instack[u]=true; 
  for(int i=0;i<edge[u].size();++i){
    int v=edge[u][i];
    if(!dfn[v]){
      Tarjan(v);
      low[u]=min(low[u],low[v]);
    }
    else if(instack[v])
      low[u]=min(low[u],dfn[v]);
  }
  if(dfn[u]==low[u]){
    ++cntb;
    int node;
    do{
      node=s.top();
      s.pop();
      instack[node]=false;
      belong[cntb].push_back(node);
    }while(node!=u);
  }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;++i){
    int u,v;
    cin>>u>>v;
    edge[u].push_back(v);
  }
  Tarjan(1);
  return 0;
}

Tarjan:割点

#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 5;
int n, m, num,root;
int dn, dfn[N], low[N], cnt, buc[N],sum; 
vector<int> e[N];
void Tarjan(int x){
  dfn[x]=low[x]=++num;
  int flag=0;
  for(int i=0;i<e[x].size();i++){
    int to=e[x][i];
    if(!dfn[to]){
      Tarjan(to);
      low[x]=min(low[x],low[to]);
      if(low[to]>=dfn[x]){
        flag++;
        if(x!=root||(flag>=2)){
          buc[x]=1;
        }
      }
    }
    else low[x]=min(low[x],dfn[to]);
  }
}
int main() {
  cin >> n >> m;
  for(int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  for(int i=1;i<=n;i++){
    if(!dfn[i]){
      root=i;
      Tarjan(i);
    } 
  }
  for(int i=1;i<=n;i++){
    if(buc[i]) sum++; 
  } 
  cout<<sum<<endl;
  for(int i=1;i<=n;i++){
    if(buc[i]) cout<<i<<" ";
  } 
  return 0;
}

Tarjan: 割边

#include<iostream>
#include<cmath>
using namespace std;
int n, m, root, a, b, total;
int e[101][101], dfn[101], low[101], flag[101], head[101];

struct node{
    int to;
    int next;
}edge[10010];

int cnt = 1;
void add(int u, int v) {
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void tarjan(int u, int father) {
    int child = 0;
    dfn[u] = low[u] = ++total;
    for (int i = head[u]; i != 0; i = edge[i].next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            child++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if  (low[v] > dfn[u]) {
                cout << u << "->" << v << endl;
            }
        } else if (v != father) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}


int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    root = 1;
    tarjan(1, root);
    for (int i = 1; i <= n; i++) {
        if(flag[i]) {
            cout << i << " ";
        }
    }
    return 0;
}

差分约束：

#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct edge {
  int v,w,next;
} e[10005];
int head[5005],tot[5005],dis[5005],vis[5005],cnt,n,m;
void addedge(int u,int v,int w) {
  e[++cnt].v=v;
  e[cnt].w=w;
  e[cnt].next=head[u];
  head[u]=cnt;
}
bool spfa(int s) {
  queue<int> q;
  memset(dis,63,sizeof(dis));
  dis[s]=0,vis[s]=1;
  q.push(s);
  while(!q.empty()) {
    int u=q.front();
    q.pop();
    vis[u]=0;
    for(int i=head[u]; i; i=e[i].next) {
      int v=e[i].v;
      if(dis[v]>dis[u]+e[i].w) {
        dis[v]=dis[u]+e[i].w;
        if(!vis[v]) {
          vis[v]=1,tot[v]++;
          if(tot[v]==n+1)return false; // 注意添加了一个超级源点
          q.push(v);
        }
      }
    }
  }
  return true;
}
int main() {
  cin>>n>>m;
  for(int i=1; i<=n; i++)
    addedge(0,i,0);
  for(int i=1; i<=m; i++) {
    int v,u,w;
    cin>>v>>u>>w;
    addedge(u,v,w);
  }
  if(!spfa(0))cout<<"NO"<<endl;
  else
    for(int i=1; i<=n; i++)
      cout<<dis[i]<<' ';
  return 0;
}

严格单元次短路:

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200010;
struct edge{
  int to,nxt,v;
}e[MAXN];
int h[MAXN],cnt,dis[2][MAXN],n,m;
void add(int u,int v,int w){
  e[++cnt].nxt=h[u];
    e[cnt].to=v; 
    e[cnt].v=w;
  h[u]=cnt;
}
struct node{
  int pos,dis;
  friend bool operator<(node a,node b){
    return a.dis>b.dis;
  }
}tmp;

priority_queue<node> q;
void dij(){
  for(int i=1;i<=n;i++){
    dis[0][i]=dis[1][i]=2147483647;
  }
  dis[0][1]=0;
  tmp.dis=0,tmp.pos=1;
  q.push(tmp);
  while(!q.empty()){
    tmp=q.top();
    q.pop();
    int u=tmp.pos,d=tmp.dis;
    if(d>dis[1][u]) continue;
    for(int i=h[u];i;i=e[i].nxt){
      int v=e[i].to;
      int w=e[i].v;
      if(dis[0][v]>d+w){
        dis[1][v]=dis[0][v];
        tmp.dis=dis[0][v]=d+w;
        tmp.pos=v;
        q.push(tmp);
      }
      if(dis[1][v]>d+w&&dis[0][v]<d+w){
        tmp.dis=dis[1][v]=d+w;
        tmp.pos=v;
        q.push(tmp);
      }
    }
  }
}
int main(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    int a,b,c;
    cin>>a>>b>>c;
    add(a,b,c);
    add(b,a,c);
  }
  
  dij();
  cout<<dis[1][n];
}

严格次小生成树：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const ll INF = 1e18;
int n, m,d[N];
bool vis[N];
ll f[N][25],g1[N][25],g2[N][25],mst, ans = INF;
struct Node {
  ll to,cost;
};
vector<Node> v[N];

void dfs(const int x) {
  vis[x] = true;
  for (int i = 0; i < v[x].size(); i++) {
    int y = v[x][i].to;
    if (vis[y]) continue;
    d[y] = d[x] + 1;
    f[y][0] = x;
    g1[y][0] = v[x][i].cost;
    g2[y][0] = -INF;
    dfs(y);
  }
}

inline void prework() {
  for (int i = 1; i <= 20; i++)
    for (int j = 1; j <= n; j++) {
      f[j][i] = f[f[j][i - 1]][i - 1];
      g1[j][i] = max(g1[j][i - 1], g1[f[j][i - 1]][i - 1]);
      g2[j][i] = max(g2[j][i - 1], g2[f[j][i - 1]][i - 1]);
      if (g1[j][i - 1] > g1[f[j][i - 1]][i - 1]) g2[j][i] = max(g2[j][i], g1[f[j][i - 1]][i - 1]);
      else if (g1[j][i - 1] < g1[f[j][i - 1]][i - 1]) g2[j][i] = max(g2[j][i], g1[j][i - 1]);
    }
}

inline void LCA(int x, int y, const ll w) {
  ll zui = -INF, ci = -INF;
  if (d[x] > d[y]) swap(x, y);
  for (int i = 20; i >= 0; i--)
    if (d[f[y][i]] >= d[x]) {
      zui = max(zui, g1[y][i]);
      ci = max(ci, g2[y][i]);
      y = f[y][i];
    }
  if (x == y) {
    if (zui != w) ans = min(ans, mst - zui + w);
    else if (ci != w && ci > 0) ans = min(ans, mst - ci + w);
    return;
  }
  for (int i = 20; i >= 0; i--)
    if (f[x][i] != f[y][i]) {
      zui = max(zui, max(g1[x][i], g1[y][i]));
      ci = max(ci, max(g2[x][i], g2[y][i]));
      x = f[x][i];
      y = f[y][i];
    }
  zui = max(zui, max(g1[x][0], g1[y][0]));
  if (g1[x][0] != zui) ci = max(ci, g1[x][0]);
  if (g2[y][0] != zui) ci = max(ci, g2[y][0]);
  if (zui != w) ans = min(ans, mst - zui + w);
  else if (ci != w && ci > 0) ans = min(ans, mst - ci + w);
}

struct Edge {
  int from, to;
  ll cost;
  bool is_tree;
} edge[N * 3];

bool operator < (const Edge x, const Edge y) {
  return x.cost < y.cost;
}

int fa[N];

inline int find(const int x) {
  if (fa[x] == x) return x;
  else return fa[x] = find(fa[x]);
}

inline void Kruskal() {
  sort(edge, edge + m);
  for (int i = 1; i <= n; i++)
    fa[i] = i;
  for (int i = 0; i < m; i++) {
    int x = edge[i].from;
    int y = edge[i].to;
    ll z = edge[i].cost;
    int a = find(x), b = find(y);
    if (a == b) continue;
    fa[find(x)] = y;
    mst += z;
    edge[i].is_tree = true;
    v[x].push_back((Node) {
      y, z
    });
    v[y].push_back((Node) {
      x, z
    });
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin >> n >> m;
  for (int i = 0, x, y; i < m; i++) {
    ll z;
    cin >> x >> y >> z;
    if (x == y) continue;
    edge[i].from = x;
    edge[i].to = y;
    edge[i].cost = z;
  }
  Kruskal();
  d[1] = 1;
  dfs(1);
  prework();
  for (int i = 0; i < m; i++)
    if (!edge[i].is_tree)
      LCA(edge[i].from, edge[i].to, edge[i].cost);
  cout << ans << "\n";
  return 0;
}

Kruskal：

#include <bits/stdc++.h>
using namespace std;
const int N=2000200;
int n,m,f[N];
long long ans=0;
struct edge{
  int u,v,c;
}e[N];
bool operator<(edge x,edge y){
  return x.c<y.c;
}
int find(int x){
  return x==f[x]?x:f[x]=find(f[x]);
}
void sovle(){
  cin>>n>>m;
  for(int i=1;i<=m;i++){
    cin>>e[i].u>>e[i].v>>e[i].c;
  }
  sort(e+1,e+m+1);
  for(int i=1;i<=n;i++) f[i]=i;
  for(int i=1;i<=m;i++){
    int fu=find(e[i].u),fv=find(e[i].v);
    if(fu==fv) continue;
    f[fu]=fv;
    ans+=e[i].c;
  }
  cout<<ans<<endl;
}

signed main(){
    sovle();
  return 0;
}

Prim：

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5010;
const int inf = 0x3f3f3f3f;
int g[maxn][maxn];
int dis[maxn];
bool vis[maxn];
int n, m, u, v, w,cnt;

int prime() {
    int tot = 0;
    memset(dis, inf, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[1] = 0;
    for (int i = 1; i <= n; ++i) {
        int minv = inf, u = -1;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && minv > dis[j]) {
                minv = dis[j];
                u = j;
            }
        }
        if (u == -1) return -1;
        vis[u] = true;
        tot += minv;
        cnt++;
        for (int j = 1; j <= n; ++j) {
            if (!vis[j] && dis[j] > g[u][j]) {
                dis[j] = g[u][j];
            }
        }
    }
    return tot;
}

int main() {
    memset(g, inf, sizeof(g));
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = min(g[u][v], w);
    }
    int tmp=prime();
    if(cnt>=n-1)
        cout << tmp << endl;
    return 0;
}

树的直径：

#include <bits/stdc++.h>
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
using namespace std;
int dp[100010]={0},ans;
vector<int> G[100010];
void dfs(int rt,int fa){
  dp[rt]=0;
  int mx=0,mn=0;
  for(int i=0;i<G[rt].size();i++){
    int to=G[rt][i];
    if(to==fa) continue;
    dfs(to,rt);
    if(dp[to]>mx){
      mn=mx;
      mx=dp[to];
    }
    else if(dp[to]>mn) mn=dp[to];
  }
  dp[rt]=mx+1;
  ans=max(ans,mx+mn);
  
}
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n-1;i++){
    int u,v;
    cin>>u>>v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  dfs(1,-1);
  cout<<ans<<endl;
  return 0;

}

树的重心：

#include <bits/stdc++.h>
using namespace std;

const int MAXN=1000010;
const int inf=0x7f7f7f7f;

int f[MAXN],size[MAXN],head[MAXN],dep[MAXN];
int n,center,sum;
vector<int> G[MAXN];
queue<int> q;

void dfs(int u,int fa){
  size[u]=1;
  f[u]=0;
  for(int i=0;i<G[u].size();i++){
    int v=G[u][i];
    if(v==fa) continue;
    dfs(v,u);
    size[u]+=size[v];
    f[u]=max(f[u],size[v]);
  }
  f[u]=max(f[u],n-size[u]);
  if(f[u]<f[center]||(f[u]==f[center]&&u<center)){
    center=u;
  }
}

void bfs(){
  q.push(center);
  while(!q.empty()){
    int u=q.front();
    q.pop();
    for(int i=0;i<G[u].size();i++){
      int v=G[u][i];
      if(dep[v]||v==center) continue;
      dep[v]=dep[u]+1;
      sum+=dep[v];
      q.push(v);
    }
  }
}
int main(){
  cin>>n;
  for(int i=1;i<=n-1;i++){
    int u,v;
    cin>>u>>v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  center=0;
  f[0]=inf;
  dfs(1,0);
  bfs();
  cout<<center<<" "<<sum<<endl; 
  return 0;
}

树的中心：

#include<bits/stdc++.h>
using namespace std;
const int N = 10010, M = N * 2, INF = 0x3f3f3f3f;
int n;
int h[N], e[M], w[M], ne[M], idx;
int d1[N], d2[N], p1[N], up[N];
bool is_leaf[N];
void add(int a, int b, int c) {
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dfs_d(int u, int father) {
    d1[u] = d2[u] = -INF;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;
        int d = dfs_d(j, u) + w[i];
        if (d >= d1[u]) {
            d2[u] = d1[u], d1[u] = d;
            p1[u] = j;
        } else if (d > d2[u]) d2[u] = d;
    }
    if (d1[u] == -INF) {
        d1[u] = d2[u] = 0;
        is_leaf[u] = true;
    }
    return d1[u];
}
void dfs_u(int u, int father) {
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        if (j == father) continue;

        if (p1[u] == j) up[j] = max(up[u], d2[u]) + w[i];
        else up[j] = max(up[u], d1[u]) + w[i];

        dfs_u(j, u);
    }
}
int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ ) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    dfs_d(1, -1);
    dfs_u(1, -1);
    int res = d1[1];
    for (int i = 2; i <= n; i ++ )
        if (is_leaf[i]) res = min(res, up[i]);
        else res = min(res, max(d1[i], up[i]));
    printf("%d\n", res);
    return 0;
}

LCA：

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
typedef pair<int,int> PII;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 5e5+10;
const int base = 233;
int n,m,s;
int pre[N][35],dep[N];
vector<int>v[N];
void init(int l,int ff){
    pre[l][0] = ff;
    dep[l] = dep[ff] + 1;
    for(int r:v[l]){
        if(r==ff)continue;
        init(r,l);
    }
}
void init(){
    init(s,0);
    for(int k=1;k<=25;k++){
        for(int i=1;i<=n;i++){
            pre[i][k] = pre[ pre[i][k-1] ][k-1];
        }
    }
}
int LCA(int x,int y){
    //1.同深度
    if(dep[x]<dep[y])swap(x,y);
    for(int k=25;k>=0;k--){
        int fa = pre[x][k];
        if(dep[fa]>=dep[y])x = fa;
    }
    if(x==y)return x;
    //2.一起向上跳 
    for(int k=25;k>=0;k--){
        int fax = pre[x][k];
        int fay = pre[y][k];
        if(fax != fay){
            x = fax;
            y = fay;
        }
    }
    return pre[y][0];
}
inline void slove(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    init();
    while (m--){
        int x,y;scanf("%d%d",&x,&y);
        printf("%d\n",LCA(x,y));
    }
}
int main(){
    int TT=1;
    while(TT--) slove();
    return 0;
}

树上差分

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
typedef pair<int,int> PII;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
const int N = 5e5+10;
const int base = 233;
int n,m,s;
int pre[N][35],dep[N],val[N];
vector<int>v[N];
void init(int l,int ff){
    dep[l] = dep[ff] + 1;
    pre[l][0] = ff;
    for(int r:v[l]){
        if(r==ff)continue;
        init(r,l);
    }
}
void init(){
    init(1,0);
    for(int k=1;k<=25;k++){
        for(int i=1;i<=n;i++){
            pre[i][k] = pre[pre[i][k-1]][k-1];
        }
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int k=25;k>=0;k--){
        if(dep[pre[x][k]]>=dep[y]) x = pre[x][k];
    }
    if(x==y)return x;
    for(int k=25;k>=0;k--){
        if(pre[x][k] != pre[y][k])x = pre[x][k],y = pre[y][k];
    }
    return pre[x][0];
}
int ans = 0;
void dfs(int l,int ff){
    for(int r:v[l]){
        if(r==ff)continue;
        dfs(r,l);
        val[l] += val[r];
    }
    ans = max(ans,val[l]);
}
inline void slove(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    init();
    while (m--){
        int x,y;scanf("%d%d",&x,&y);
        val[x]++;
        val[y]++;
        int LCA = lca(x,y);
        val[LCA]--;
        val[pre[LCA][0]]--;
    }
    dfs(1,0);
    printf("%d\n",ans);
}
int main(){
    int TT=1;
    while(TT--)slove();
    return 0;
}

最长上升子序列：

\(O(n^2)\)

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,a[100005],dp[100005],MAX;
  cin>>n; 
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++){
    MAX=0;
    for(int j=1;j<=i-1;j++)
      if(a[i]>a[j]) MAX=max(MAX,dp[j]);
    dp[i]=MAX+1;
  }
  MAX=0;
  for(int i=1;i<=n;i++) MAX=max(MAX,dp[i]);
  cout<<MAX<<endl;
}

\(O(nlogn)\)

#include <bits/stdc++.h>
using namespace std;
int a[10005],f[10005];
int cnt;
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  for(int i=1;i<=n;i++){
        int pos=lower_bound(f+1,f+cnt+1,a[i])-f;
        if(pos==cnt+1) f[++cnt]=a[i];
        else f[pos]=a[i];
  }
  cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++) cout<<f[i]<<" ";
  return 0;
}

最长公共子序列：

\(O(n^2)\)

#include<iostream>
using namespace std;
int dp[1001][1001],a1[2001],a2[2001],n,m;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a1[i]);
    for(int i=1;i<=n;i++)scanf("%d",&a2[i]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {
        dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        if(a1[i]==a2[j])
        dp[i][j]=max(dp[i][j],dp[i-1][j-1]+1);
      }
    cout<<dp[n][n];
}

\(O(nlogn)\)

#include<bits/stdc++.h>
using namespace std;
int a[100001],b[100001],mp[100001],f[100001];
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++){
            cin>>a[i];
            mp[a[i]]=i;
    }
  for(int i=1;i<=n;i++){
          cin>>b[i];
          f[i]=0x7fffffff;
    }
  int len=0;
  f[0]=0;
  for(int i=1;i<=n;i++){
    int l=0,r=len,mid;
    if(mp[b[i]]>f[len])f[++len]=mp[b[i]];
    else
    {
        int pos=lower_bound(f,f+len,mp[b[i]])-f;
            f[pos]=min(mp[b[i]],f[pos]);
      }
    }
    cout<<len;
    return 0;
}

01背包：

空间复杂度 \(O(nV)\)

#include <bits/stdc++.h>
using namespace std;
int f[1005][1005];    //f[i][j]表示选前i个物品重量不超过j的最大值
int main(){
  int n,V;
  cin>>n>>V;
  for(int i=1;i<=n;i++){
    int v,w;
    cin>>v>>w;
    for(int j=1;j<=V;j++){
      if(v<=j) 
        f[i][j]=max(f[i-1][j],f[i-1][j-v]+w); 
      else
        f[i][j]=f[i-1][j];
    } 
  }
  cout<<f[n][V]<<endl;
  return 0;
}

空间复杂度 \(O(V)\)

#include <bits/stdc++.h>
using namespace std;
int f[1005];
int main(){
  int n,V;
  cin>>n>>V;
  for(int i=1;i<=n;i++){
    int v,w;
    cin>>v>>w;
    for(int j=V;j>=v;j--) f[j]=max(f[j],f[j-v]+w);
  }
  cout<<f[V]<<endl;
  return 0;
}

二维费用01背包

#include <iostream>
using namespace std;
const int N = 110;
int n, V, M,f[N][N];
int main(){
    cin >> n >> V >> M;
    for (int i = 0; i < n; i ++ ){
        int v, m, w;
        cin >> v >> m >> w;
        for (int j = V; j >= v; j -- )
            for (int k = M; k >= m; k -- )
                f[j][k] = max(f[j][k], f[j - v][k - m] + w);
    }
    cout << f[V][M] << endl;
    return 0;
}

01背包求具体方案：

#include <iostream>
using namespace std;
const int N = 1010;
int n, m,v[N], w[N],f[N][N];
int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    for (int i = n; i >= 1; i -- )   //要求输出字典序最小所以考虑倒着做，即 f[1][m] 为最大价值
        for (int j = 0; j <= m; j ++ ){
            f[i][j] = f[i + 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
        }
    int j = m;
    for (int i = 1; i <= n; i ++ )
        if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]){
            cout << i << ' ';
            j -= v[i];
        }
    return 0;
}

完全背包：

空间复杂度 \(O(nV)\)

#include <bits/stdc++.h>
using namespace std;
int f[1005][1005];    
int main(){
  int n,V;
  cin>>n>>V;
  for(int i=1;i<=n;i++){
    int v,w;
    cin>>v>>w;
    for(int j=0;j<=V;j++){
        f[i][j]=f[i-1][j];
        if(v<=j) 
            f[i][j]=max(f[i][j],f[i][j-v]+w); 
    } 
  }
  cout<<f[n][V]<<endl;
  return 0;
}

空间复杂度 \(O(V)\)

#include <bits/stdc++.h>
using namespace std;
int f[1005];
int main(){
  int n,V;
  cin>>n>>V;
  for(int i=1;i<=n;i++){
    int v,w;
    cin>>v>>w;
    for(int j=v;j<=V;j++) f[j]=max(f[j],f[j-v]+w);
  }
  cout<<f[V]<<endl;
  return 0;
}

多重背包：

时间复杂度 \(O(nVs)\) (朴素版)

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int v[N], w[N], s[N],f[N][N],n, m;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];
    for(int i = 1; i <= n; i ++){//枚举背包
        for(int j = 1; j <= m; j ++){//枚举体积
            for(int k = 0; k <= s[i]; k ++)
                if(j >=  k * v[i])
                    f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    }
    cout << f[n][m] << endl;
    return 0;
}

时间复杂度 \(O(n \ logs V)\) (二进制分解)

#include<bits/stdc++.h>
using namespace std;
const int N = 12010, M = 2010;
int n, m,v[N], w[N],f[M];
int main(){
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for(int i = 1;i <= n;i ++){
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while(k<=s){
            cnt ++ ; //组别先增加
            v[cnt] = a * k ; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if(s>0){
            cnt ++ ;
            v[cnt] = a*s; 
            w[cnt] = b*s;
        }
    }
    n = cnt ; //枚举次数正式由个数变成组别数
    //01背包一维优化
    for(int i = 1;i <= n ;i ++)
        for(int j = m ;j >= v[i];j --)
            f[j] = max(f[j],f[j-v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

时间复杂度 \(O(nV)\) (单调队列优化)

#include<bits/stdc++.h>
using namespace std;
const int N = 20010;
int n, m,f[N], g[N], q[N];
int main(){
    cin >> n >> m;
    for (int i = 0; i < n; i ++ ){
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);   //滚动数组
        for (int j = 0; j < v; j ++ ){
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v){    //单调队列求区间最大值
                if (hh <= tt && q[hh] < k - s * v) hh ++ ;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }
    cout << f[m] << endl;
    return 0;
}

分组背包：

\(O(nms)\)

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N],v[N][N],w[N][N],s[N],n,m,k;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++)
            cin>>v[i][j]>>w[i][j];
    }
    for(int i=0;i<n;i++){   //枚举组
        for(int j=m;j>=0;j--){
            for(int k=0;k<s[i];k++){    //for(int k=s[i];k>=0;k--)也可以
                if(j>=v[i][k])     f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);  
            }
        }
    }
    cout<<f[m]<<endl;
}

分组背包求具体方案

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int f[N][N],g[N][N],res[N];   //g[i][j] 为第i组的体积为j的价值
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    for(int i=n;i;i--)    //要求输出字典序最小所以考虑倒着做，即 f[1][m] 为最大价值
        for(int j=0;j<=m;j++)
            for(int k=0;k<=j;k++)
                f[i][j]=max(f[i][j],f[i+1][j-k]+g[i][k]);
    cout<<f[1][m]<<endl;
    int j=m;
    for(int i=1;i<=n;i++)
        for(int k=0;k<=j;k++)
            if(f[i][j]==f[i+1][j-k]+g[i][k]){
                res[i]=k;
                j-=k;
                break;
            }
    for(int i=1;i<=n;i++)
        cout<<i<<" "<<res[i]<<endl;
    return 0;
}

其他dp

2.2.5 数学与其他

康托展开：

#include<cstdio>
using namespace std;
#define N 1000001
int n,tr[N];
long long ans,fac[N];
void add(int x,int k) {
	for (; x<=n; x+=x&-x) tr[x]+=k;
}
int query(int x) {
	int t=0;
	for (; x; x-=x&-x) t+=tr[x];
	return t;
}
int main() {
	scanf("%d",&n);
	fac[0]=1;
	for (int i=1; i<=n; i++) {
		fac[i]=fac[i-1]*i%998244353;
		add(i,1);
	}
	for (int i=1,x; i<=n; i++) {
		scanf("%d",&x);
		ans=(ans+(query(x)-1)*fac[n-i])%998244353;
		add(x,-1);
	}
	printf("%lld",ans+1);
	return 0;
}

中国剩余定理：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10;
int n;
int A[N], B[N];
LL exgcd(LL a, LL b, LL &x, LL &y)  // 扩展欧几里得算法, 求x, y，使得ax + by = gcd(a, b){
	if (!b){
		x = 1; y = 0;
		return a;
	}
	LL d = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return d;
}
int main(){
	scanf("%d", &n);
	LL M = 1;
	for (int i = 0; i < n; i ++ ){
		scanf("%d%d", &A[i], &B[i]);
		M *= A[i];
	}
	LL res = 0;
	for (int i = 0; i < n; i ++ )
	{
		LL Mi = M / A[i];
		LL ti, x;
		exgcd(Mi, A[i], ti, x);
		res = (res + (__int128)B[i] * Mi * ti) % M;
		// B[i] * Mi * ti可能会超出long long范围，所以需要转化成__int128
	}
	cout << (res % M + M) % M << endl;
	return 0;
}

线性筛：

void work(int n){
	numlist[1]=1;
	for(int i=2;i<=n;i++){
		if(numlist[i]==false) prime[++cnt]=i;
		for(int j=1; j<=cnt&&i*prime[j]<=n; j++){
			numlist[i*prime[j]] = true ;
			if(i%prime[j]==0) break;
		} 
	}
}

欧拉筛

int st[N]; // 初始化为0， 0表示质数，1表示合数
for(int i = 2; i <= n; i++){
	for(int j = 2; j <= i / j; j++){
		if(i % j == 0){
			st[i] = 1; 
		}
	}
}

快速幂：

int qmi(int a, int k){
	int res = 1;
	while (k){
		if (k & 1) res = (LL)res * a % mod;
		a = a * a % mod;
		k >>= 1;
	}
	return res;
}

欧拉函数：

void init(int n)
{
	phi[1] = 1;
	for (int i = 2; i <= n; i ++ )
	{
		if (!st[i])
		{
			primes[cnt ++ ] = i;
			phi[i] = i - 1;
		}
		for (int j = 0; primes[j] * i <= n; j ++ )
		{
			st[i * primes[j]] = true;
			if (i % primes[j] == 0)
			{
				phi[i * primes[j]] = phi[i] * primes[j];
				break;
			}
			phi[i * primes[j]] = phi[i] * (primes[j] - 1);
		}
	}
}

拓展欧几里得：

int exgcd(int a, int b, int &x, int &y)
{
	if (!b)
	{
		x = 1, y = 0;
		return a;
	}

	int d = exgcd(b, a % b, y, x);
	y -= a / b * x;

	return d;
}

逆元

费马小定理求逆元：

  LL pow_mod(LL a, LL b, LL p){//a的b次方求余p 
	  LL ret = 1;
	  while(b){
		  if(b & 1) ret = (ret * a) % p;
		  a = (a * a) % p;
		  b >>= 1;
	  }
	  return ret;
  }
  LL Fermat(LL a, LL p){//费马求a关于b的逆元 
		  return pow_mod(a, p-2, p);
  }

扩展欧基里德求逆元:

  #include<cstdio>
  typedef long long LL;
  void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
	  if (!b) {d = a, x = 1, y = 0;}
	  else{
		  ex_gcd(b, a % b, y, x, d);
		  y -= x * (a / b);
	  }
  }
  LL inv(LL t, LL p){//如果不存在，返回-1 
	  LL d, x, y;
	  ex_gcd(t, p, x, y, d);
	  return d == 1 ? (x % p + p) % p : -1;
  }
  int main(){
	  LL a, p;
	  while(~scanf("%lld%lld", &a, &p)){
		  printf("%lld\n", inv(a, p));
	  }
  }

线性求逆元：

	Inv[ 1 ] = 1;
	for( int i = 2; i <= n; i++ )
		Inv[ i ] = ( p - p / i ) * Inv[ p % i ] % p;

组合数：

杨辉三角：

#include <iostream>
using namespace std;
typedef long long LL;
const int N = 2010, MOD = 1e9+7;
int n;
int c[N][N];
void init() {
    for (int i = 0; i < N; ++i) 
        for (int j = 0; j <= i; ++j)
            if (!j) c[i][j] = 1;
            else c[i][j] = (c[i-1][j] + c[i-1][j-1]) % MOD;
}
int main() {
    init();
    int n;
    cin >> n;
    while (n --) {
        int a, b;
        cin >> a >> b;
        cout << c[a][b] << endl;
    }
    return 0;
}

预处理阶乘+逆元：

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 1e5+5, MOD = 1e9+7;
int fact[N], infact[N];
int qmi(int a, int k, int p) {
    LL res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        k >>= 1;
        a = (LL)a * a % p;
    }
    return res;
}
int main() {
    fact[0] = infact[0] = 1;
    for (int i = 1 ; i < N; ++i) {
        fact[i] = (LL)fact[i - 1] * i % MOD;
        infact[i] = (LL)infact[i - 1] * qmi(i, MOD - 2, MOD) % MOD;
    }
    
    int n;
    cin >> n;
    while (n --) {
        int a, b;
        cin >> a >> b;
        
        cout << (LL)fact[a] * infact[a - b] % MOD * infact[b] % MOD << endl;
    }
    return 0;
}

Lucas定理

#include <iostream>
using namespace std;
typedef long long LL;
int qmi(int a, int k, int p) {
    int res = 1 % p;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}
// 定义求解
int C(int a, int b, int p) {
    if (b > a) return 0;
    int res = 1;
    for (int i = 1, j = a; i <= b; ++i, --j) {
        res = (LL)res * j % p;
        res = (LL)res * qmi(i, p - 2, p) % p;
    }
    return res;
}
int lucas(LL a, LL b, LL p) {               // 注意LL参数类型
    if (a < p && b < p) return C(a, b, p);
    return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;     // 递归让其到p范围内求解
}
int main() {
    int n;
    cin >> n;
    
    while (n --) {
        LL a, b, p;
        cin >> a >> b >> p;
        cout << (LL)lucas(a, b, p) << endl;
    }
    return 0;
}

高斯消元：

#include <iostream>
#include <cmath>
using namespace std;
const int N = 105;
const double eps = 1e-6;
int n;
double a[N][N];
int gauss() {
    int c, r;
    for (c = 0, r = 0; c < n; ++c) {        // c列r行，遍历列
        int t = r;
        for (int i = r; i < n; ++i)         // 寻找列主元，拿t记录
            if (fabs(a[i][c]) > fabs(a[t][c])) 
                t = i;              
        if (fabs(a[t][c]) < eps) continue;  // 如果列主元为0，不必考虑，当前列全为0
        
        // 交换列主元t行与当前r行的数
        for (int i = c; i < n + 1; ++i) swap(a[t][i], a[r][i]); 
        // 当前列主元已经被交换到了r行，需要从后向前进行处理，避免主对角线元素变成1
        for (int i = n; i >= c; --i) a[r][i] /= a[r][c]; 
        // 列主消元
        for (int i = r + 1; i < n; ++i) 
            if (fabs(a[i][c]) > eps)
                for (int j = n; j >= c; --j) 
                    a[i][j] -= a[r][j] * a[i][c];     
        ++r;
    }
    if (r < n) {
        for (int i = r; i < n; ++i) 
            if (fabs(a[i][n]) > eps) return 2;  // 0x=1 则无解
        
        return 1;   // 0x=0 无穷多解
    }
    // 上三角阶梯型矩阵
    // 直接求解即可，最后一列放置结果
    for (int i = n - 1; i >= 0; --i)    
        for (int j = i + 1; j < n; ++j) 
            a[i][n] -= a[j][n] * a[i][j];
    return 0;
}
int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < n + 1; ++j) 
            cin >> a[i][j];
    int t = gauss();
    if (t == 0) {
        for (int i = 0; i < n; ++i) printf("%.2lf\n", a[i][n]);
    } 
    else if (t == 1) puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}

龟速乘

LL qmul(LL a, LL k, LL p) {
    LL res = 0;
    while (k){
        if (k & 1) res = (res + a) % p;
        a = (a + a) % p; 
        k >>= 1;
    }
    return res;
}

莫比乌斯函数

mu[1]=1;
for(i=2;i<=n;i++){
    if(!not_prime[i]){
        prime[++tot]=i;
        mu[i]=-1;
    }
    for(j=1;prime[j]*i<=n;j++){
        not_prime[prime[j]*i]=1;
        if(i%prime[j]==0){
            mu[prime[j]*i]=0;
            break;
        }
        mu[prime[j]*i]=-mu[i];
    }
}

标签：std,数据结构,return,int,tr,++,include,CSP,模板
From： https://www.cnblogs.com/fanrunze/p/18328525

CSP-S提高组数据结构算法模板大合集

CSP-S 算法总结

2.2.1 基础知识与编程环境

2.2.2 C++ 程序设计 2

2.2.3 数据结构

2.2.4 算法

基数排序

归并排序

二分图的判定：

DAG拓扑排序：

Dijkstra \(O((n+m)\times log(n+m))\)

SPFA：

Floyd:

Bellman-Ford:

Kosaraju:

Tarjan(强连通分量):

Tarjan:割点

Tarjan: 割边

差分约束：

严格单元次短路:

严格次小生成树：

Kruskal：

Prim：

树的直径：

树的重心：

树的中心：

LCA：

树上差分

最长上升子序列：

\(O(n^2)\)

\(O(nlogn)\)

最长公共子序列：

\(O(n^2)\)

\(O(nlogn)\)

01背包：

空间复杂度 \(O(nV)\)

空间复杂度 \(O(V)\)

二维费用01背包

01背包求具体方案：

完全背包：

空间复杂度 \(O(nV)\)

空间复杂度 \(O(V)\)

多重背包：

时间复杂度 \(O(nVs)\) (朴素版)

时间复杂度 \(O(n \ logs V)\) (二进制分解)

时间复杂度 \(O(nV)\) (单调队列优化)

分组背包：

\(O(nms)\)

分组背包求具体方案

2.2.5 数学与其他

康托展开：

中国剩余定理：

线性筛：

欧拉筛

快速幂：

欧拉函数：

拓展欧几里得：

逆元

费马小定理求逆元：

扩展欧基里德求逆元:

线性求逆元：

组合数：

杨辉三角：

预处理阶乘+逆元：

Lucas定理

高斯消元：

龟速乘

莫比乌斯函数

相关文章

赞助商

阅读排行