C++算法模板总结

· · 算法·理论

排序

冒泡排序

//a为待排序数组，len为数组长度，数组下标从1开始 
for(int i = 1;i<=len;i++){
    for(int j = 1 ;j<=len-i;j++){
        if(a[j]>a[j+1]){
            int t ;
            t = a[j];
            a[j]= a[j+1];
            a[j+1]=t;   
            //以上四行代码可用swap(a[j],a[j+1])代替 
        }
    }
}

选择排序

for(int i=1;i<=n;i++){
    int k=i;//k为最小的数的编号 
    for(int j=i+1;j<=n;j++){
        if(a[j]<a[k]){
            k=j;
        }
    }
    if(k!=i){
        int t;
        t = a[i];
        a[i]=a[k];
        a[k] = t;
        //以上四行可以用swap(a[i],a[k])代替 
    }
}

插入排序

for(int i=1;i<n;i++){
    if(a[i]<a[i-1]){
        int j=i-1;
        int x=a[i];
        while(j>-1&&x<a[j]){ 
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=x; 
    }
}

快速排序

建议直接用sort

如果你想手敲，那就随便吧

#include <iostream>
using namespace std;
int a[10000],n,k;
void pai(int start,int end,bool flag){
    int i=start,j=end;
    if (start>=end){
        return ;
    }
    while (i!=j){
        if (flag){
            while (a[j]>=a[start]&&j>i){
                j--;
            }
        }
        else{
            while (a[j]<=a[start]&&j>i){
                j--;
            }
        }
        if (flag){
            while (a[i]<=a[start]&&i<j){
                i++;
            }
        }
        else{
            while (a[i]>=a[start]&&i<j){
                i++;
            }
        }
        int t;
        t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    int t;
    t=a[start];
    a[start]=a[i];
    a[i]=t;
    pai(start,i-1,flag);
    pai(j+1,end,flag);
}
int main(){
    cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    cin>>k;
    pai(1,n,false);
    cout<<a[k];
    return 0;
}

归并排序(代码由adminh提供)

void sort_f(int x,int y){
    if(x>=y)return ;
    int m=(y-x>>1)+x;
    sort_f(x,m);
    sort_f(1+m,y);
    for(int i=x;i<=y;i++)c[i]=a[i];
    int k=x,l=m+1;
    for(int i=x;i<=y;i++)
    if(k<=m&&(l>y||c[k]<=c[l]))a[i]=c[k++];
    else a[i]=c[l++],ans+=m-k+1;
}

搜索

深度优先搜索

图上深度优先搜索

#include <iostream>
#include <vector>
using namespace std;
vector<int> G[110];
bool vis[110];
void dfs(int u){
    vis[u]=true;
    cout<<u<<endl;
    for (int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if (!vis[v]){
            dfs(v);
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1);
    return 0;
}

求连通块数量

#include <iostream>
#include <vector>
using namespace std;
vector<int> G[110];
bool vis[110];
void dfs(int u) {
    vis[u] = true;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (!vis[v]) {
            dfs(v);
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int cnt=0;
    for (int i=1;i<=n;i++){
        if (!vis[i]){
            cnt++;
            dfs(i);
        }
    }
    cout<<cnt<<endl;
    return 0;
}

树上深度优先搜索

#include <iostream>
#include <vector>
using namespace std;
vector <int> G[105];
void dfs(int u, int fa) {
    cout<<u<<endl;
    for (int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if (v!=fa){
            dfs(v,u);
        }
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    return 0;
}

求树上节点的深度

#include <iostream>
#include <vector>
using namespace std;
vector<int> G[110];
int d[110];
void dfs(int u,int fa){
    d[u]=d[fa]+1;
    for (int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if (v!=fa){
            dfs(v,u);
        }
    }
}
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0);
    for (int i=1;i<=n;i++){
        cout<<i<<" "<<d[i]<<endl;
    }
    return 0;
}

求解子树大小

#include <iostream>
#include <vector>
using namespace std;
vector<int> G[110];
int sz[110];
int dfs(int u, int fa) {
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v != fa) {
            sz[u]+=dfs(v,u);
        }
    }
    sz[u]++;
    return sz[u];
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= n; i++) {
        cout << i << " " << sz[i] << endl;
    }
    return 0;
}

枚举全排列

#include <iostream>
using namespace std;
const int N = 20;
int n;
int per[N];
bool vis[N];
void dfs (int dep) {
    if (dep==n){
        for (int i=0;i<n;i++){
            cout<<per[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for (int i=1;i<=n;i++){
        if (vis[i]){
            continue;
        }
        per[dep]=i;
        vis[i]=true;
        dfs(dep+1);
        vis[i]=false;
    }
}

int main() {
    cin >> n;
    dfs(0);
    return 0;
}

枚举K排列

#include <iostream>
using namespace std;
const int N = 20;
int n, k;
int per[N];
bool vis[N];
void dfs (int dep) {
    if (dep == k) {
        for (int i = 0; i < k; i++) {
            cout << per[i] << " ";
        }
        cout << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) {
          continue;
        }
        per[dep] = i;
        vis[i] = true;
        dfs(dep + 1);
        vis[i] = false;
    }
}

int main() {
    cin >> n >> k;
    dfs(0);
    return 0;
}

枚举组合

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 15;
int n, k;
int comb[N];
void dfs(int x, int dep) {
    if (dep==k){
        for (int i=0;i<k;i++){
            cout<<comb[i]<<" ";
        }
        cout<<endl;
        return;
    }
    if (x>n){
        return;
    }
    comb[dep]=x;
    dfs(x+1,dep+1);
    dfs(x+1,dep);
}
int main() {
    cin >> n >> k;
    dfs(1,0);
    return 0;
}

求n个数中选k个数使得和为sum的方案数问题（去重版）

#include <iostream>
using namespace std;
int n, k, sum, ans;
int a[40];
bool xuan[40];
void dfs(int s,int cnt){
    if (s==sum && cnt==k){
        ans++;
    }
    for (int i=0;i<n;i++){
        if (!xuan[i]){
            xuan[i]=1;
            dfs(s+a[i],cnt+1);
            xuan[i]=0;
        }
    }
}
int main() {
    cin >> n >> k >> sum;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    ans=0;
    dfs(0,0);
    for (int i=1;i<=k;i++){
        ans/=i;
    }
    cout<<ans<<endl;
    return 0;
}

求解八皇后问题

#include <iostream>
using namespace std;
int ans = 0;
bool row[10],x1[20],x2[20];
int v[10];
bool check(int i,int c){
    return !row[i] && !x1[i+c] && !x2[i-c+8];
}
void dfs(int c){
    if (c==8){
        ans++;
        for (int i=0;i<8;i++){
            for (int j=0;j<8;j++){
                if (v[j]==i){
                    cout<<"Q";
                }
                else{
                    cout<<".";
                }
            }
            cout<<endl;
        }
        cout<<endl;
        return;
    }
    for (int i=0;i<8;i++){
        if (check(i,c)){
            row[i]=x1[i+c]=x2[i-c+8]=true;
            v[c]=i;
            dfs(c+1);
            row[i]=x1[i+c]=x2[i-c+8]=false;
            // v[c]=-1;
        }
    }
}
int main() {
    dfs(0);
    cout<<ans<<endl;
    return 0;    
}

广度优先搜索

求无权图的最短路

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<int> G[105];
queue<int> q;
int dis[105];
void bfs(int s) {
    memset(dis,-1,sizeof(dis));
    dis[s]=0;
    q.push(s);
    while (!q.empty()){
        int now=q.front();
        q.pop();
        for (int i=0;i<G[now].size();i++){
            int v=G[now][i];
            if (dis[v]==-1){
                dis[v]=dis[now]+1;
                q.push(v);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(1);
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << endl;
    }
    return 0;
}

多起点的广度优先搜索

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<int> G[105];
queue<int> q;
int dis[105];
void bfs() {
    memset(dis, -1, sizeof(dis));
    dis[1]=0;
    q.push(1);
    dis[5]=0;
    q.push(5);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < G[now].size(); i++) {
            int v = G[now][i];
            if (dis[v] == -1) {
                dis[v] = dis[now] + 1;
                q.push(v);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs();
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << endl;
    }
    return 0;
}

求每个点到终点的最短路

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int n, m;
vector<int> G[105];
queue<int> q;
int dis[105];
int bfs(int s) {
    memset(dis, -1, sizeof(dis));
    dis[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for (int i = 0; i < G[now].size(); i++) {
            int v = G[now][i];
            if (dis[v] == -1) {
                dis[v] = dis[now] + 1;
                q.push(v);
            }
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[v].push_back(u);
    }
    bfs(n);
    for (int i = 1; i <= n; i++) {
        cout << dis[i] << " ";
    }
    cout << endl;
    return 0;
}

动态规划

求最大子段和

#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1000000000;
int a[105], dp[105], ans = -inf;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i=1;i<=n;i++){
        if (dp[i-1]>=0){
            dp[i]=dp[i-1]+a[i];
        }
        else{
            dp[i]=a[i];
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

求最长上升子序列

#include <iostream>
#include <algorithm>
using namespace std;
int a[1005], dp[1005], ans;
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i=1;i<=n;i++){
        dp[i]=1;
        for (int j=1;j<i;j++){
            if (a[j]<a[i]){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}

求最长公共子序列(LCS)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int dp[1005][1005];
int main() {
    string a, b;
    cin >> a >> b;
    for (int i=1;i<=a.size();i++){
        for (int j=1;j<=b.size();j++){
            if (a[i-1]==b[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout<<dp[a.size()][b.size()];
    return 0;
}

背包问题

01背包

未优化版

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

int dp[21][1010];
int w[21], c[21];
int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= V; j++) {
            if (j >= c[i]) {
                dp[i][j]=max(dp[i-1][j-c[i]]+w[i],dp[i-1][j]);
            } else {
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

空间优化版

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[1010];
int w[21], c[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    int flag = 1;
    for (int i = 1; i <= N; i++) {
        for (int j=V;j>=c[i];j--){
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
        }
    }
    cout<<dp[V];
    return 0;
}

多重背包

未优化版

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

int dp[21][1010];
int w[21], c[21], n[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; ++i) {
        cin >> w[i] >> c[i] >> n[i];
    }
    for (int i=1;i<=N;i++){
        for (int j=0;j<=V;j++){
            for (int k=0;k<=n[i];k++){
                if (j>=k*c[i]){
                    dp[i][j]=max(dp[i][j],dp[i-1][j-k*c[i]]+k*w[i]);
                }
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

空间优化版

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

int dp[1010];
int w[21], c[21], n[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i] >> n[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j=V;j>=0;j--) {
            for (int k = 0; k <= n[i]; k++) {
                if (j >= c[i] * k) {
                    dp[j] = max(dp[j - c[i] * k] + w[i] * k, dp[j]);
                }
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}

完全背包

未优化版

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

int dp[21][1010];
int w[21], c[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    for (int i=1;i<=N;i++){
        for (int j=0;j<=V;j++){
            if (j>=c[i]){
                dp[i][j]=max(dp[i][j-c[i]]+w[i],dp[i-1][j]);
            }
            else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout << dp[N][V] << endl;
    return 0;
}

空间优化版

#include <iostream>
using namespace std;

int dp[1010];
int w[21], c[21];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> w[i] >> c[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = c[i]; j <= V; j++) {
            dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
        }
    }
    cout << dp[V] << endl;
    return 0;
}

背包可行性判定

#include <iostream>
using namespace std;

bool dp[110][1010];
int c[110];

int main() {
    int N, V;
    cin >> N >> V;
    for (int i = 1; i <= N; i++) {
        cin >> c[i];
    }
    dp[0][0]=1;
    for (int i=1;i<=N;i++){
        for (int j=0;j<=V;j++){
            if (j<c[i]){
                dp[i][j]=dp[i-1][j];
            }
            else{
                dp[i][j]=dp[i-1][j] || dp[i-1][j-c[i]];
            }
        }
    }
    if (dp[N][V]){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}

多维限制背包

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

int dp[1010][1010];
int v[21], w[21], c[21];
int main() {
    int N, V, W;
    cin >> N >> V >> W;
    for (int i = 1; i <= N; i++) {
        cin >> v[i] >> w[i] >> c[i];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = V; j >= v[i]; j--) {
            for (int k = W; k >= w[i]; k--) {
                dp[j][k]=max(dp[j][k],dp[j-v[i]][k-w[i]]+c[i]);
            }
        }
    }
    cout << dp[V][W] << endl;
    return 0;
}

图论

链式前向星

struct Edge {//建结构体，maxm为题目要求的最大边数，maxn为题目要求的最大节点数
    int to, next, dis;
} edge[maxm * 2];//无向图一定一定要*2，否则可能会导致丢分
int h[maxn], tot;
void addEdge(int x, int y, int len) {//建边
    edge[++tot] = {y, h[x], len};
    h[x] = tot;
}
for (int i = h[x]; i; i = edge[i].next) {//遍历边
    // 以下省略一个地球
}

最短路

Floyd算法

#include <bits/stdc++.h>
using namespace std;
const int N = 101;
int g[N][N], n, m, u, v, w;;
int main() {
    memset(g, 0x3f, sizeof(g));
    for (int i = 0; i < N; i++) g[i][i] = 0;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    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]);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << g[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

dijkstra算法(堆优化版)

普通版

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
const int M = 10101;
const int inf = 0x3f3f3f3f;
struct Edge {
    int to, next, len;
} e[M * 2];
int h[N], tot, n, m, s, d[N];
bool vis[N];
set<pair<int, int>> heap;
void addEdge(int x, int y, int len) {
    e[++tot] = {y, h[x], len};
    h[x] = tot;
}
void dijkstra(int s) {
    memset(d, 0x3f, sizeof(d));
    memset(vis, 0, sizeof(vis));
    d[s] = 0;
    heap.insert({0,s});
    while (heap.size()){
        int v=heap.begin()->second;
        heap.erase(heap.begin());
        for (int i=h[v];i;i=e[i].next){
            int to=e[i].to;
            if (d[to]>d[v]+e[i].len){
                heap.erase({d[to],to});
                d[to]=d[v]+e[i].len;
                heap.insert({d[to],to});
            }
        }
    }
}
int main() {
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    dijkstra(s);
    for (int i = 1; i <= n; i++) {
        cout << d[i] << " ";
    }
    return 0;
}

优先队列版(代码由Scez提供)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100050,M=500050; 
int n,m,s;
int u,v,w;
struct edge{
    int to,next,w;
}e[M];
int head[N],cnt;
int dis[N];
struct node{
    int dis,id;
    bool operator <(const node &x)const
    {
        return x.dis<dis;
    }
};
void add(int u,int v,int w)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    e[cnt].w=w;
    head[u]=cnt;
}
priority_queue<node> q;
int vis[N];
void dij()
{
    q.push((node){0,s});
    for(int i=2;i<=n;i++)
    dis[i]=0x3f3f3f3f;
    while(!q.empty())
    {
        node now=q.top();
        q.pop();
        if(vis[now.id])
        continue;
        vis[now.id]=1;
        for(int i=head[now.id];i;i=e[i].next)
        {
            int p=e[i].to;
            if(dis[p]>dis[now.id]+e[i].w)
            {
                dis[p]=dis[now.id]+e[i].w;
                if(!vis[p])
                q.push((node){dis[p],p});
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s;
    while(m--)
    {
        cin>>u>>v>>w;
        add(u,v,w);
    }
    dij();
    for(int i=1;i<=n;i++)
    {
        cout<<dis[i]<<" ";
    }
    return 0;
}

SPFA算法

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
const int M = 10101;
const int inf = 0x3f3f3f3f;
struct Edge {
    int to, next, len;
} e[M * 2];
int h[N], tot, n, m, s, d[N], inq[N];
queue<int> q;
void addEdge(int x, int y, int len) {
    e[++tot] = {y, h[x], len};
    h[x] = tot;
}
void spfa(int s) {
    memset(d, 0x3f, sizeof(d));
    memset(inq, 0, sizeof(inq));
    d[s] = 0;
    inq[s]=true;
    q.push(s);
    while (!q.empty()){
        int v=q.front();
        q.pop();
        inq[v]=false;
        for (int i=h[v];i;i=e[i].next){
            int to=e[i].to;
            if (d[to]>d[v]+e[i].len){
                d[to]=d[v]+e[i].len;
                if (!inq[to]){
                    q.push(to);
                    inq[to]=true;
                }
            }
        }
    }
}
int main() {
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    spfa(s);
    for (int i = 1; i <= n; i++) {
        cout << d[i] << " ";
    }
    return 0;
}

并查集(路径压缩后)

#include <iostream>
using namespace std;
int fa[110];
int n, m;
void init() {//初始化fa数组
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int get(int x) {//查找x所在集合的代表
    if (fa[x] == x) {
        return x;
    }
    fa[x]=get(fa[x]);//路径压缩
    return fa[x];
}
void merge(int x, int y) {//合并x所在的集合和y所在的集合
    x = get(x);
    y = get(y);
    if (x != y) {
        fa[y] = x;
    }
}
int main() {
    cin >> n >> m;
    init();
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (fa[i]==i) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

最小生成树

kruskal算法

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1100; // 最大顶点数
const int M = 100100; // 最大边数
struct Edge {// 使用结构体储存每一条边，便于排序
    int u, v, w; // 表示有一条 (u,v) 的无向边，边权为 w
} e[M];
int ecnt;// 用于边表计数
void addEdge(int u, int v, int w){ // 加入一条无向边
    e[++ecnt] = {u, v, w};
}
int fa[N]; // 并查集相关
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]); // 路径压缩
}
int n; // 顶点数
bool cmp(const Edge &a, const Edge &b){
    return a.w < b.w;
}
int Kruskal() { // Kruskal 算法核心过程
    for (int i = 1; i <= n; i++) {
        fa[i] = i; // 初始化并查集
    }
    sort(e+1,e+ecnt+1,cmp);
    int sum=0,cnt=0;
    for (int i=1;i<=ecnt;i++){
        int u=e[i].u,v=e[i].v;
        u=find(u);
        v=find(v);
        if (u!=v){
            fa[u]=v;
            sum+=e[i].w;
            cnt++;
        }
    }
    if (cnt!=n-1){
        return -1;
    }
    return sum;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int w;
            cin >> w;
            addEdge(i, j, w);
        }
    }
    cout << Kruskal();
    return 0;
}

prim算法

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1001;
const int maxm = 10101;
const int inf = 0x3f3f3f3f;
struct Edge {
    int to, next, len;
} edge[maxm * 2];
int h[maxn], tot = -1;
int n, m, s;
int d[maxn];
bool vis[maxn];
void addEdge(int x, int y, int len) {
    edge[++tot] = {y, h[x], len};
    h[x] = tot;
}
int prim() {
    memset(d, 0x3f, sizeof(d));
    d[s] = 0;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        int mind = inf;
        int v = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < mind) {
                mind = d[j];
                v = j;
            }
        }
        if (mind == inf) {
            break;
        }
        vis[v] = true;
        sum += d[v];
        for (int j = h[v]; j != -1; j = edge[j].next) {
            int to = edge[j].to;
            d[to] = min(d[to], edge[j].len);
        }
    }
    return sum;
}
int main() {
    cin >> n >> m >> s;
    memset(h, -1, sizeof(h));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }
    cout << prim() << endl;
    return 0;
}

求树的重心

#include <iostream>
using namespace std;
const int N = 50010; // 结点个数
struct Edge { // 临接表储存
    int to, next;
} G[2 * N]; // 无向边，所以需要开双倍的边表
int head[N], ecnt;// 用于边表计数
void addEdge(int u, int v) {
    G[++ecnt] = {v, head[u]};
    head[u] = ecnt;
}
int n;
int siz[N],f[N];
void dfs(int u,int fa){
    siz[u]=1;
    f[u]=0;
    for (int i=head[u];i;i=G[i].next){
        int v=G[i].to;
        if (v==fa){
            continue;
        }
        dfs(v,u);
        siz[u]+=siz[v];
        f[u]=max(f[u],siz[v]);
    }
    f[u]=max(f[u],n-siz[u]);
}
int main() {
    cin >> n;
    int u, v;
    for (int i = 1; i < n; i++) {
        cin >> u >> v; // 读入树
        addEdge(u, v); // 无向边插入两次
        addEdge(v, u);
    }
    int id = 1;
    dfs(1,1);
    for (int i = 2; i <= n; i++) {
        if (f[i] < f[id]) {
            id = i;
        }
    }
    cout << id << " " << f[id] << endl;
    return 0;
}

求树的直径

#include <iostream>
using namespace std;
const int N = 50010;
struct Edge{
    int to, next;
} G[2 * N];
int head[N], ecnt;
void addEdge(int u, int v) {
    G[++ecnt] = {v, head[u]};
    head[u] = ecnt;
}
int len, id;
void dfs(int u, int fa, int dis) {
    if (dis > len) {
        len = dis;
        id = u;
    }
    for (int i=head[u];i;i=G[i].next){
        int v=G[i].to;
        if (v==fa){
            continue;
        }
        dfs(v,u,dis+1);
    }
}
int main() {
    int n;
    cin >> n;
    int u, v;
    for (int i = 1; i < n; i++) {
        cin >> u >> v; // 读入树
        addEdge(u, v); // 无向边插入两次
        addEdge(v, u);
    }
    len=0;
    id=1;
    dfs(1,1,0);
    int x=id;
    len=0;
    id=x;
    dfs(x,x,0);
    cout<<len;
    return 0;
}

拓扑排序

非字典序最小版

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
const int maxm = 100010;
vector<int> G[maxn];
int rd[maxn];
void addEdge(int u, int v) {
    G[u].push_back(v);
    rd[v]++;
}
int seq[maxn];
bool toposort(int n) {
    queue<int> q;
    for (int i=1;i<=n;i++){
        if (rd[i]==0){
            q.push(i);
        }
    }
    int ncnt=0;
    while (!q.empty()){
        int u=q.front();
        q.pop();
        seq[++ncnt]=u;
        for (int i=0;i<G[u].size();i++){
            int v=G[u][i];
            rd[v]--;
            if (rd[v]==0){
                q.push(v);
            }
        }
    }
    return ncnt==n;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }
    if (!toposort(n)) {
        puts("Not DAG");
    } else {
        for (int i = 1; i <= n; i++) {
            printf("%d%c", seq[i], i == n ? '\n' : ' ');
        }
    }
    return 0;
}

字典序最小版

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10010;
const int maxm = 100010;
vector <int> G[maxn];
int deg[maxn];
void addEdge(int u, int v) {
    G[u].push_back(v);
    deg[v]++;
}
int seq[maxn];
bool toposort(int n) {
    priority_queue<int,vector<int>,greater<int>> q;
    for (int i = 1; i <= n; i++) {
        if (deg[i] == 0) {
            q.push(i);
        }
    }
    int ncnt = 0;
    while (!q.empty()) {
        int u = q.top();
        q.pop();
        seq[++ncnt] = u;
        for (int i = 0; i < G[u].size(); i++){
            int v = G[u][i];
            deg[v] -= 1;
            if(deg[v] == 0) {
                q.push(v);
            }
        }
    }
    return ncnt == n;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    int u, v;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d", &u, &v);
        addEdge(u, v);
    }
    if (!toposort(n)) {
        puts("Not DAG");
    } else {
        for (int i = 1; i <= n; i++) {
            printf("%d%c", seq[i], i == n ? '\n' : ' ');
        }
    }
    return 0;
}

求解欧拉路径

#include <bits/stdc++.h>
using namespace std;
struct node {
    int v, id;
};
vector<node> G[105];
int fa[105], in[105], out[105];
int n, m, f, cntout, cntin, start;
stack<int> s;
bool vis[10005];
void init() {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int get(int x) {
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
        fa[y] = x;
        f--;
    }
}
int euler() {
    for (int i = 1; i <= n; i++) {
        if (out[i] == 0 && in[i] == 0) {
            f--;
        }
    }
    if (f != 1) {
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        if (out[i] - in[i] == 1) {
            cntout++;
        } else if (out[i] - in[i] == -1) {
            cntin++;
        } else if (out[i] != in[i]) {
            return 0;
        }
    }
    if (cntout == 0 && cntin == 0) {
        return 1;
    } else if (cntout == 1 && cntin == 1) {
        for (int i = 1; i <= n; i++) {
            if (out[i] - in[i] == 1) {
                return i;
            }
        }
    } else {
        return 0;
    }
}
void dfs(int u) {
    if (out[u]){
        for (int i=0;i<G[u].size();i++){
            if (!vis[G[u][i].id]){
                vis[G[u][i].id]=true;
                out[u]--;
                dfs(G[u][i].v);
            }
        }
    }
    s.push(u);
}
int main() {
    cin >> n >> m;
    init();
    f = n;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back({v, i});
        merge(u, v);
        out[u]++;
        in[v]++;
    }
    start = euler();
    if (start) {
        dfs(start);
        while (!s.empty()){
            cout<<s.top()<<endl;
            s.pop();
        }
    } else {
        cout << "No" << endl;
    }
    return 0;
}

注：这份代码多了判断图是否连通的部分，如果题目中保证图是连通的，可以省去很多代码

最近公共祖先（LCA）

#include <cstring>
#include <iostream>
using namespace std;
const int MAX_N = 100005;
const int MAX_M = 200005;
struct Edge {
    int v, next;
} e[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v) {
    e[eid].v = v;
    e[eid].next = p[u];
    p[u] = eid++;
}
int f[MAX_N][20], d[MAX_N];
void dfs(int u) {
    d[u]=d[f[u][0]]+1;
    for (int i = p[u]; i != -1; i = e[i].next) {
        int v = e[i].v;
        if (v == f[u][0]) {
            continue;
        }
        f[v][0]=u;
        dfs(v);
    }
}
int lca(int x,int y){
    if (d[x]<d[y]){
        swap(x,y);
    }
    int K=0;
    while ((1<<(K+1))<=d[x]){
        K++;
    }
    for (int j=K;j>=0;j--){
        if (d[f[x][j]]>=d[y]){
            x=f[x][j];
        }
    }
    if (x==y){
        return x;
    }
    for (int j=K;j>=0;j--){
        if (f[x][j]!=f[y][j]){
            x=f[x][j];
            y=f[y][j];
        }
    }
    return f[x][0];
}
int main() {
    int n, q;
    cin >> n >> q;
    init();
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        insert(u, v);
        insert(v, u);
    }
    dfs(1);
    for (int j=1;(1<<j)<=n;j++){
        for (int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
    return 0;
}

进制转换

任意进制转十进制

#include <iostream>
#include <cmath>
using namespace std;
int main(){
    int a;
    cin>>a;
    int b[100];
    string n[100];
    for (int i=1;i<=a;i++){
        cin>>b[i]>>n[i];
    }
    for (int i=1;i<=a;i++){
        int jieguo=0;
        for (int j=n[i].size()-1;j>=0;j--){
            if (n[i][j]=='A'){
                jieguo+=10*pow(b[i],n[i].size()-1-j);
            }
            else if (n[i][j]=='B'){
                jieguo+=11*pow(b[i],n[i].size()-1-j);
            }
            else if (n[i][j]=='C'){
                jieguo+=12*pow(b[i],n[i].size()-1-j);
            }
            else if (n[i][j]=='D'){
                jieguo+=13*pow(b[i],n[i].size()-1-j);
            }
            else if (n[i][j]=='E'){
                jieguo+=14*pow(b[i],n[i].size()-1-j);
            }
            else if (n[i][j]=='F'){
                jieguo+=15*pow(b[i],n[i].size()-1-j);
            }
            else{
                jieguo+=(n[i][j]-'0')*pow(b[i],n[i].size()-1-j);
            }
        }
        cout<<jieguo<<endl;
    }
    return 0;
}

十进制转任意进制

#include <iostream>
#include <cstring>
using namespace std;
int main(){
    int b[100];
    int n[100];
    int a;
    cin>>a;
    for (int i=1;i<=a;i++){
        cin>>b[i]>>n[i];
    }
    for (int i=1;i<=a;i++){
        string jieguo;
        int j=1;
        while (n[i]>=b[i]){
            int c=n[i]%b[i];
            if (c==10){
            jieguo[j]='A';
            }
            else if (c==11){
                jieguo[j]='B';
            }
            else if (c==12){
                jieguo[j]='C';
            }
            else if (c==13){
                jieguo[j]='D';
            }
            else if (c==14){
                jieguo[j]='E';
            }
            else if (c==15){
                jieguo[j]='F';
            }
        else{
            jieguo[j]=c+'0';
        }
            n[i]=n[i]/b[i];
            j++;
        }
        if (n[i]==10){
            jieguo[j]='A';
        }
        else if (n[i]==11){
            jieguo[j]='B';
        }
        else if (n[i]==12){
            jieguo[j]='C';
        }
        else if (n[i]==13){
            jieguo[j]='D';
        }
        else if (n[i]==14){
            jieguo[j]='E';
        }
        else if (n[i]==15){
            jieguo[j]='F';
        }
        else{
            jieguo[j]=n[i]+'0';
        }
        for (int k=j;k>=1;k--){
            cout<<jieguo[k];
        }
        cout<<endl;
    }
    return 0;
}

高精度

高精度加法

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
    string a1,b1;
    int a[10000],b[10000],c[10000],lena,lenb,lenc,i,x=0;
    cin>>a1>>b1;
    lena=a1.length();
    lenb=b1.length();
    for (int i=0;i<lena;i++){
        a[lena-i]=a1[i]-48;
    }
    for (int i=0;i<lenb;i++){
        b[lenb-i]=b1[i]-48;
    }
    lenc=0;
    while (lenc<=lena||lenc<=lenb){
        c[lenc]=a[lenc]+b[lenc]+x;
        if (c[lenc]>=10){
            c[lenc]=c[lenc]%10;
            c[lenc+1]=1;
            x=1;
        }
        else{
            x=0;
        }
        lenc++;
    }
    if (a[lenc]==0){
        lenc--;
    }
    for (int i=lenc;i>=1;i--){
        cout<<c[i];
    }
    return 0;
}

高精度计算器(来自OI Wiki)

#include <cstdio>
#include <cstring>

static const int LEN = 1004;

int a[LEN], b[LEN], c[LEN], d[LEN];

void clear(int a[]) {
  for (int i = 0; i < LEN; ++i) a[i] = 0;
}

void read(int a[]) {
  static char s[LEN + 1];
  scanf("%s", s);

  clear(a);

  int len = strlen(s);
  for (int i = 0; i < len; ++i) a[len - i - 1] = s[i] - '0';
}

void print(int a[]) {
  int i;
  for (i = LEN - 1; i >= 1; --i)
    if (a[i] != 0) break;
  for (; i >= 0; --i) putchar(a[i] + '0');
  putchar('\n');
}

void add(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    c[i] += a[i] + b[i];
    if (c[i] >= 10) {
      c[i + 1] += 1;
      c[i] -= 10;
    }
  }
}

void sub(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    c[i] += a[i] - b[i];
    if (c[i] < 0) {
      c[i + 1] -= 1;
      c[i] += 10;
    }
  }
}

void mul(int a[], int b[], int c[]) {
  clear(c);

  for (int i = 0; i < LEN - 1; ++i) {
    for (int j = 0; j <= i; ++j) c[i] += a[j] * b[i - j];

    if (c[i] >= 10) {
      c[i + 1] += c[i] / 10;
      c[i] %= 10;
    }
  }
}

bool greater_eq(int a[], int b[], int last_dg, int len) {
  if (a[last_dg + len] != 0) return true;
  for (int i = len - 1; i >= 0; --i) {
    if (a[last_dg + i] > b[i]) return true;
    if (a[last_dg + i] < b[i]) return false;
  }
  return true;
}

void div(int a[], int b[], int c[], int d[]) {
  clear(c);
  clear(d);

  int la, lb;
  for (la = LEN - 1; la > 0; --la)
    if (a[la - 1] != 0) break;
  for (lb = LEN - 1; lb > 0; --lb)
    if (b[lb - 1] != 0) break;
  if (lb == 0) {
    puts("> <");
    return;
  }

  for (int i = 0; i < la; ++i) d[i] = a[i];
  for (int i = la - lb; i >= 0; --i) {
    while (greater_eq(d, b, i, lb)) {
      for (int j = 0; j < lb; ++j) {
        d[i + j] -= b[j];
        if (d[i + j] < 0) {
          d[i + j + 1] -= 1;
          d[i + j] += 10;
        }
      }
      c[i] += 1;
    }
  }
}

int main() {
  read(a);

  char op[4];
  scanf("%s", op);

  read(b);

  switch (op[0]) {
    case '+':
      add(a, b, c);
      print(c);
      break;
    case '-':
      sub(a, b, c);
      print(c);
      break;
    case '*':
      mul(a, b, c);
      print(c);
      break;
    case '/':
      div(a, b, c, d);
      print(c);
      print(d);
      break;
    default:
      puts("> <");
  }

  return 0;
}

其它

判断是否是质数

bool isprime(int a){
    if (a<=1){
        return false;
    }
    for (int i=2;i*i<=a;i++){
        if (a%i==0){
            return false;
        }
    }
    return true;
}

两数的最大公约数

int gcd(int a,int b){
    if (b==0){
        return a;
    }
    return gcd(b,a%b);
}

后续正在施工中，敬请期待！

如果您还有其他模板，但此处没有，可以评论或者私信我，我都会加上的

编写不易，给个点赞+关注支持一下，多谢！

感谢用户Scez、adminh提供了部分代码

本文总计字符数：35242