526互联

程序设计实践基础算法模板

发布时间 2023-11-30 11:52:31作者: rrobber

程设 复习 代码

1.kruscal

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100000

struct rec{int x,y,z;} edge[500010];
int fa[100010], n, m, ans;
bool operator <(rec a, rec b) {
    return a.z < b.z;
}
int get(int x){
    if(x == fa[x])    return x;
    return fa[x] = get(fa[x]);
}
int main() {
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].z);
    //按照边权排序
    sort(edge + 1, edge + m + 1);
    //并查集初始化
    for (int i = 1; i <= n; i ++)    fa[i] = i;
    //求最小生成树  牛牛冲冲冲！
    for (int i = 1; i <= m; i ++){
        int x = get(edge[i].x);
        int y = get(edge[i].y);
        if (x == y)        continue;
        fa[x] = y;
        ans += edge[i].z;
    }
    cout << ans << endl;
}

2.可能头文件

#include<bits/stdc++.h>  //万能头文件，但是会拖慢程序运行速度
#include<cstdio>
#include <cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>

#include <list>　　　　　　//STL 线性列表容器
#include <map>　　　　　　 //STL 映射容器
#include <utility>　　　　 //STL 通用模板类
#include <vector>　　　　　//STL 动态数组容器
#include <stack>　　　　　 //STL 堆栈容器　　　　

3.prim算法

int a[3010][3010], d[3010], n, m, ans;
bool v[3010];

void prim(){
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    d[1] = 0;
    for(int i = 1; i < n; i++){
        int x = 0;
        for (int j = 1; j <= n; j++)
            if(!v[j] && (x == 0 || d[j] < d[x]))
                x = j;
        v[x] = 1;
        for(int y = 1; y <= n; y++)
            if(!v[y])
                d[y] = min(d[y], a[x][y]);
    }
}

int main(){
    cin >> n >> m;
    //构建邻接矩阵
    memset(a, 0x3f, sizeof(a));
    for(int i = 1; i <= n; i++)    a[i][i] = 0;
    for(int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[y][z] = a[x][y] = min(a[x][y], z);
    }
    //求最小生成树
    prim();
    for(int i = 2; i <= n; i++)    ans += d[i];
    cout << ans << endl;
}

4.dijkstra算法

int a[3010][3010], d[3010], n, m, ans;
bool v[3010];

void dijkstra(){
    memset(d, 0x3f, sizeof(d)); //dist数组
    memset(v, 0, sizeof(v));  //节点标记
    d[1] = 0;
    for(int i = 1; i < n; i++){ //重复进行n-1次
        int x = 0;
        //找到未标记节点中dist最小的
        for (int j = 1; j <= n; j++)
            if(!v[j] && (x == 0 || d[j] < d[x]))
                x = j;
        v[x] = 1;
        //用全局最小值x更新其他节点
        for(int y = 1; y <= n; y++)
            if(!v[y])
                d[y] = min(d[y], d[x] + a[x][y]);
    }
}

int main(){
    cin >> n >> m;
    //构建邻接矩阵
    memset(a, 0x3f, sizeof(a));
    for(int i = 1; i <= n; i++)    a[i][i] = 0;
    for(int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = min(a[x][y], z);
    }
    //求单源最短路径 （抄的手累）
    dijkstra();
    for(int i = 1; i <= n; i++)    
        printf("%d\n", d[i]);
}

5.Floyd算法

int d[310][310], n, m;
int main(){
    cin >> n >> m;
    //把d数组初始化为邻接矩阵
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; i++)    d[i][i] = 0;
    for (int i = 1; i <= m; i++){
        int x, y, z;
        scanf("%d%d%d",&x,&y,&z);
        d[x][y] = min(d[x][y], z);
    }
    //floyd求任意两点路径
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j =1; j<= n; j++)
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    //输出
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)    printf("%d ",d[i][j]);
        puts("");
    }

}

6.BST

（1）BST的建立

struct BST{
    int l,r; //左右子节点在数组中的下标
    int val; //节点关键码
} a[SIZE];//数组模拟链表
int tot, root, INF = 1<<30;

int New(int val) {
    a[++tot].val = val;
    return tot;
}
void Build() {
    New(-INF),New(INF);
    root = 1, a[1].r = 2;
}

（2）BST的检索

int Get(int p, int val){
    if (p == 0)    return 0; //检索失败
    if (val == a[p].val)    return p; //检索成功
    return val < a[p].val ? Get(a[p].l, val) : Get(a[p].r, val);
}

（3）BST的插入

void Insert(int &p, int val){
    if (p == 0) {
        p = New(val); //p是引用，其父节点的r与l值会被同时更新
        return;
    }
    if (val == a[p].val)    return;
    if (val < a[p].val)    Insert(a[p].l, val);
    else    Insert(a[p].r, val);
}

（4）BST求前驱/后缀

int GetNext(int val){
    int ans = 2; //a[2].val==INF
    int p = root;
    while(p){
        if(val == a[p].val) {//检索成功 tired…
            if(a[p].r > 0) {//有右子树
                p = a[p].r;
                //右子树上一直向左走
                while (a[p].l > 0)    p = a[p].l;
                ans = p;
            }
            break;
        }
        //每经过一个节点都尝试更新后缀
        if(a[p].val > val && a[p].val < a[ans].val)    ans = p;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    return ans;
}

（5）BST节点删除

void Remove(int val) {
    //检索val,得到节点p
    int &p = root;
    while(p) {
        if (val == a[p].val)    break;
        p = val < a[p].val ? a[p].l : a[p].r;
    }
    if(p == 0)    return;
    if (a[p].l == 0) {    //没有左子树
        p = a[p].r; //右子树代替p位置，注意p是引用
    }
    else if (a[p].r == 0){ //没有右子树
        p = a[p].l; //左子树代替P位置，注意p是引用
    }
    else{//既有左子树又有右子树
        //求后继结点
        int next = a[p].r;
        while(a[next].l > 0)    next = a[next].l;
        //next 一定没有左子树，直接删除
        Remove(a[next].val);
        //令节点next代替节点p的位置
        a[next].l = a[p].l, a[next].r = a[p].r;
        p = next; //p是引用
    }
}

（6）Treap

void zig(int &p){//右旋
    int q = a[p].l;
    a[p].l = a[q].r, a[q].r = p;
    p = q;//p是引用
}

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

7.二分

（1）在单调递增序列a中查找>=x的数中最小的一个

while(l < r){
    int mid = (l + r) >> 1;
    if(a[mid] >= x)    r = mid; 
    else    l = mid + 1;
}
return a[l];

（2）在单调递增序列a中查找<=x的数中最大的一个

while(l < r){
    int mid = (l + r + 1) >> 1;
    if(a[mid] <= x)    l = mid;
    else    r = mid - 1;
}
return a[l];

（3）二分答案

// 把n本书分成m组，每组厚度之和<=size，是否可行
bool valid(int size) {
    int group = 1, rest = size;
    for(int i = 1; i <= n; i++){
        if (rest >= a[i])    rest -= a[i];
        else group++, rest = size - a[i];
    }
    return group <= m;
}

int main(){
    //二分答案，判断“每组厚度之和不超过二分的值”时
    //能否在m组内把书分完
    int l = 0, r = sum_of_ai;
    while(l < r){
        int mid = (l + r) / 2;
        if (valid(mid))    r = mid;
        else    l = mid + 1;
    }
    cout << l << endl;
}

8.DFS

int c[20], cab[20], n, w, ans;
void dfs(int now, int cnt) {
    if(cnt >= ans)    return;
    if(now == n + 1) {
        ans = min(ans, cnt);
        return;
    }
    for (int i = 1; i <= cnt; i++){//分配到已租用缆车
        if (cab[i] + c[now] <= w) { //能装下
            cab[i] += c[now];
            dfs(now+1, cnt);
            cab[i] -= c[now]; // 还原现场
        }
    }
    cab[cnt +1] = c[now];
    dfs(now + 1, cnt + 1);
    cab[cnt + 1] = 0;
}

int main(){
    cin >> n >> w;
    for(int i = 1; i <= n; i++)    cin >> c[i];
    sort(c + 1, c + n + 1);
    reverse(c + 1, c + n + 1);
    ans = n; //最多用n辆缆车，每辆猫一辆
    dfs(1,0);
    cout << ans << endl;
}

9.0/1背包问题

int f[MAX_M+1];
memset(f, 0x3f, sizeof(f));
f[0] = 0;
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]);
int ans = 0;
for(int j = 0; j <= m; j++)
    ans = max(ans, f[j]);