头像

封禁用户

初一蒟蒻QwQ求$\Huge\color{red}{AK}$ $$CSP2022 \color{red}{RP++}$$




离线:8小时前


最近来访(19636)
用户头像
微雨双飞燕
用户头像
StarLi9ht
用户头像
梦若浮生
用户头像
曾先生
用户头像
bre
用户头像
_coding
用户头像
潮鸣
用户头像
cjh20090318
用户头像
shuaige
用户头像
迎风飘扬
用户头像
taoxy
用户头像
想想yxc要怎么做
用户头像
stamina_zeng
用户头像
yxc的小迷妹
用户头像
Royal
用户头像
18910310021
用户头像
小huohuo
用户头像
AC天
用户头像
我是xdy
用户头像
holy_crap

新鲜事 原文

我回来啦 悲


新鲜事 原文

到达酒店 明天NOIP-RP++!


新鲜事 原文

准备出发NOIP!RP++!



“进阶”
如何用线段树查询某个区间 $[l,r]$ 中是 $x$ 的倍数的数的个数?
在线等



新鲜事 原文



新鲜事 原文

开心~ CSP-S2022 RP++ 晋级NOIP RP++!



$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

Bellman-Ford 算法:
有点S*的算法

  1. 循环 $n$ 次。
  2. 每层循环循环每条边,使用三角不等式进行松弛操作。
  3. 可以处理负权边,判断负环。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n, m, k;
int dist[N], back[N];
struct Edge {
    int a, b, c;
} edge[M];

int bellman_ford() {
    dist[1] = 0;
    for (int i = 1; i <= k; i++) {
        memcpy(back, dist, sizeof dist);
        for (int j = 1; j <= m; j++) {
            int a = edge[j].a, b = edge[j].b, w = edge[j].c;
            dist[b] = min(dist[b], back[a] + w);
        }
    }
    if (dist[n] >= 0x3f3f3f3f / 2) return -0x3f3f3f3f;
    return dist[n];
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        edge[i] = {u, v, w};
    }
    memset(dist, 0x3f3f3f3f, sizeof dist);
    int ans = bellman_ford();
    if (ans == -0x3f3f3f3f) puts("impossible");
    else printf("%d", ans);
    return 0;
}



$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

Bellman-Ford 算法:
有点S*的算法

  1. 循环 $n$ 次。
  2. 每层循环循环每条边,使用三角不等式进行松弛操作。
  3. 可以处理负权边,判断负环。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 510, M = 1e4 + 10;
int n, m, k;
int dist[N], back[N];
struct Edge {
    int a, b, c;
} edge[M];

int bellman_ford() {
    dist[1] = 0;
    for (int i = 1; i <= k; i++) {
        memcpy(back, dist, sizeof dist);
        for (int j = 1; j <= m; j++) {
            int a = edge[j].a, b = edge[j].b, w = edge[j].c;
            dist[b] = min(dist[b], back[a] + w);
        }
    }
    if (dist[n] >= 0x3f3f3f3f / 2) return -0x3f3f3f3f;
    return dist[n];
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        edge[i] = {u, v, w};
    }
    memset(dist, 0x3f3f3f3f, sizeof dist);
    int ans = bellman_ford();
    if (ans == -0x3f3f3f3f) puts("impossible");
    else printf("%d", ans);
    return 0;
}



$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

AcWing 849. Dijkstra求最短路 I进行堆优化。

堆优化手写堆参照AcWing 839. 模拟堆
当然可以用优先队列,但是可惜优先队列不能控制元素个数(
所以优先队列中可能会出现 $m$ 个元素。
但是可以 AC 了。

由于这题是稀疏图,因此要采用链式前向星进行存储。
时间复杂度 $O(m~\log~n)$。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
    memset(d, 0x3f3f3f3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    q.push({0, 1});
    while (q.size()) {
        int x = q.top().second;
        q.pop();
        if (st[x]) continue;
        st[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i =1 ; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra();
    if (d[n] != 0x3f3f3f3f) cout<<d[n];
    else puts("-1");
}



$$\color{red}{算法}\color{blue}{基础课}\color{purple}{笔记and题解}\color{green}{汇总}$$

AcWing 849. Dijkstra求最短路 I进行堆优化。

堆优化手写堆参照AcWing 839. 模拟堆
当然可以用优先队列,但是可惜优先队列不能控制元素个数(
所以优先队列中可能会出现 $m$ 个元素。
但是可以 AC 了。

由于这题是稀疏图,因此要采用链式前向星进行存储。
时间复杂度 $O(m~\log~n)$。

代码:

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 1000010;
int head[N], ver[M], edge[M], nxt[M], d[N];
bool st[N];
int n, m, tot;
priority_queue< pair<int, int> > q;
void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
void dijkstra() {
    memset(d, 0x3f3f3f3f, sizeof d);
    memset(st, 0, sizeof st);
    d[1] = 0;
    q.push({0, 1});
    while (q.size()) {
        int x = q.top().second;
        q.pop();
        if (st[x]) continue;
        st[x] = 1;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                q.push({-d[y], y});
            }
        }
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i =1 ; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        add(x, y, z);
    }
    dijkstra();
    if (d[n] != 0x3f3f3f3f) cout<<d[n];
    else puts("-1");
}