我的算法模板

目录

1.堆优化dijkstra

2.Bellman-Ford

3.SPFA

4.单调队列优化多重背包

---

1.堆优化dijkstra

#include <bits/stdc++.h>
using namespace std;
#define f(i, j, k) for(int i = j; i <= k; i++)
#define rf(i, j, k) for(int i = j; i >= k; i--)
#define maxn 500001
struct { int to, w, next; }edge[maxn];
int tot = 1, head[maxn], n, m, s, path[maxn];//链式前向星存图
bool visit[maxn];
void add(int n, int m, int w);
void dijkstra(int i);
int main()
{
    cin >> n >> m >> s;
    f(i, 1, m) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
    }
    dijkstra(s);//s为起始地址
    return 0;
}
void add(int n, int m, int w)
{
    edge[tot].to = m;
    edge[tot].w = w;
    edge[tot].next = head[n];
    head[n] = tot++;
}
void dijkstra(int i)//from i to every code
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q;
    memset(visit, false, sizeof(visit));
    memset(path, 0x3f, sizeof(path));
    path[i] = 0;
    q.push(make_pair(0, i));//first is weight,second is code number
    while(!q.empty()) {
        int x = q.top().second; q.pop();
        if (visit[x]) continue;
        visit[x] = true;
        for (int u = head[x]; u; u = edge[u].next) {//松弛
            if (path[x] + edge[u].w < path[edge[u].to]) {//松弛成功
                path[edge[u].to] = path[x] + edge[u].w;
                q.push(make_pair(path[edge[u].to], edge[u].to));
            }
        }
    }
    f(i, 1, n)
        cout << path[i] << ' ';
}

2.Bellman-Ford

#include <bits/stdc++.h>
using namespace std;
#define f(i, j, k) for(int i = j; i <= k; i++)
#define rf(i, j, k) for(int i = j; i >= k; i--)
#define mmin(i, j) i = min(i, j)
#define maxn 500001
struct { int from, to, w; }edge[maxn];//边集数组
int tot = 1, n, m, s, path[maxn];
void bellmanford(int s);
int main()
{
    cin >> n >> m >> s;
    f(i, 1, m) {
        int a, b, c; cin >> a >> b >> c;
        edge[tot].from = a; edge[tot].to = b; edge[tot++].w = c;
    }
    bellmanford(s);
    return 0;
}
void bellmanford(int s)
{
    memset(path, 0x3f, sizeof(path));
    path[s] = 0;
    f(i, 1, n - 1) f(j, 1, tot - 1) mmin(path[edge[j].to], path[edge[j].from] + edge[j].w);
    f(i, 1, n) if (path[i] == 0x3f3f3f3f) cout << 2147483647 << ' ';
    else cout << path[i] << ' ';
}

3.SPFA

#include <bits/stdc++.h>
using namespace std;
#define f(i, j, k) for(int i = j; i <= k; i++)
#define rf(i, j, k) for(int i = j; i >= k; i--)
#define mmin(i, j) i = min(i, j)
#define maxn 500001
struct { int to, w, next; }edge[maxn];
int tot = 1, n, m, s, path[maxn], head[maxn];
bool visit[maxn];
queue<int>q;
void add(int n, int m, int w);
void spfa(int s);
int main()
{
    cin >> n >> m >> s;
    f(i, 1, m) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
    }
    spfa(s);
    return 0;
}
void add(int n, int m, int w)
{
    edge[tot].to = m;
    edge[tot].w = w;
    edge[tot].next = head[n];
    head[n] = tot++;
}
void spfa(int s)
{
    memset(path, 0x3f, sizeof(path));
    path[s] = 0;
    memset(visit, false, sizeof(visit));
    visit[s] = true;//visit记录是否在队列中
    q.push(s);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        visit[x] = false;
        for (int u = head[x]; u; u = edge[u].next) {
            if (path[edge[u].to] > path[x] + edge[u].w) {
                path[edge[u].to] = path[x] + edge[u].w;
                if (!visit[edge[u].to]) {
                    visit[edge[u].to] = true;
                    q.push(edge[u].to);
                }
            }
        }
    }
    f(i, 1, n) if (path[i] == 0x3f3f3f3f) cout << 2147483647 << ' ';
    else cout << path[i] << ' ';
}

4.单调队列优化多重背包

#include <bits/stdc++.h>
using namespace std;
#define f(i, j, k) for(int i = j; i <= k; i++)
#define rf(i, j, k) for(int i = j; i >= k; i--) 
#define dp(i, j) dp[i][j]
int dp[20001], que[20001], sdp[20001];
int main()
{
    int N, V; cin >> N >> V;
    f(i, 1, N) {
        int v, w, s; cin >> v >> w >> s;
        memcpy(sdp, dp, sizeof(dp));
        //v为体积 w为权 s为数量
        f(r, 0, v - 1) {
            int hh = 0, tt = -1;
            for (int k = 0; r + k * v <= V; k++) {
                if (hh <= tt && k - que[hh] > s) hh++;
                while (hh <= tt && sdp[r + k * v] - k * w >= sdp[r + que[tt] * v] - que[tt] * w) tt--;
                que[++tt] = k;
                dp[r + k * v] = sdp[r + que[hh] * v] - que[hh] * w + k * w;
            }
        }
    }
    cout << dp[V] << endl;
    return 0;
}