个人空间 - AcWing

CODE_HUNTER

Freedom

关注数

粉丝数

阅读量

2986

+关注发消息

离线：29分钟前

最近来访(116)

三笘さん

Donlonboy_5

荀彧_2

荀彧_3

Mathison

Biu_78

七友_4

Serendipity_14

szn419

wcyyyooo

Wu.

waar

fangy

fammia

蓝天之约

haishangmuxucao

Atropstern

给你一记脑瓜崩

无语未央

camel

分享算法站外优质博客/题解膜

CODE_HUNTER
32分钟前

用于日后记录一些我翻到的大佬们的优质博客/题解，冲！

2023.3.30 图论的小技巧以及扩展 来自chr大佬

活动打卡代码 AcWing 854. Floyd求最短路（算法基础课）

CODE_HUNTER
57分钟前

Floyd 模板
三重循环 k, i, j

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

const int N = 210, INF = 0x3f3f3f3f;
int g[N][N];
int n;

void floyd(){
    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]);
            }
        }
    }
}

int main(){
    int m, k;
    scanf("%d%d%d", &n, &m, &k);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j) g[i][j] = 0;
            else g[i][j] = INF;
        }
    }
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = min(g[a][b], c);
    }
    floyd();
    while(k--){
        int a, b;
        scanf("%d%d", &a, &b);
        if(g[a][b]>INF/2) printf("impossible\n");
        else printf("%d\n", g[a][b]);
    }
    return 0;
}

活动打卡代码 AcWing 852. spfa判断负环（算法基础课）

CODE_HUNTER
1小时前

SPFA判断负环模板
本题可以背过！几个记忆点如下：

无需初始化dist数组，有负边就会更新。
由于不知道哪些点可以到达负环，最初需要将所有点入队。
cnt[i]记录当前到达i点的最短路的长度，如果某次更新后长度大于等于n，则路径必存在环。可以更新距离的环必为负环，故直接返回true。

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

const int N = 10010;
int h[N], e[N], w[N], ne[N], idx = 1;
int dist[N], st[N], cnt[N]; //cnt记录最短路径长度
int n, m;

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

bool spfa(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i] = 1;
    }
    while(q.size()){
        int a = q.front();
        q.pop();
        st[a] = 0;
        for(int i=h[a];i;i=ne[i]){
            int b = e[i];
            if(dist[b]>dist[a]+w[i]){
                dist[b] = dist[a]+w[i];
                cnt[b] = cnt[a]+1;
                if(cnt[b]>=n) return true;
                if(!st[b]){
                    q.push(b);
                    st[b] = 1;
                }
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d", &n, &m);
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    if(spfa()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

活动打卡代码 AcWing 851. spfa求最短路（算法基础课）

CODE_HUNTER
1小时前

SPFA 模板
四种求最短路方法的对比：

Dijkstra单源正权最短路：贪心逐点添加（可以使用堆优化）
Bellman-Ford单源最短路（可负权）：n次循环遍历所有边（第i次循环求的长度不超过i的最短路，因此可求有长度限制的最短路，但注意更新时需要使用备份的dist数组，防止路径串连）
SPFA单源最短路（可负权）：队列优化的Bellman-Ford，dist更新的点入队，继续更新后续节点（容易被卡成最坏情况）
Floyd多源最短路（可负权）：基于DP的三重循环

一般用SPFA判断负环。（Bellman-Ford也可）

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

const int N = 100010;
int h[N], e[N], w[N], ne[N], idx = 1;
int dist[N], st[N];
int n, m;

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

void spfa(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    st[1] = 1;
    while(q.size()){
        int a = q.front();
        q.pop();
        st[a] = 0;
        for(int i=h[a];i;i=ne[i]){
            int b = e[i];
            if(dist[b]>dist[a]+w[i]){
                dist[b] = dist[a]+w[i];
                if(!st[b]){
                    q.push(b);
                    st[b] = 1;
                }
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    spfa();
    if(dist[n]==0x3f3f3f3f) printf("impossible\n");
    else printf("%d\n", dist[n]);
    return 0;
}

活动打卡代码 AcWing 903. 昂贵的聘礼（算法提高课）

CODE_HUNTER
11小时前

虚拟源点直接表示点权 + 反向建图 + 枚举区间
图论的关键问题还是在建图上，多积累经验吧。

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

const int N = 110;
int g[N][N], L[N];
int dist[N], st[N];
int n, m;
int minL, maxL;

void dijkstra(int k){
    memset(dist, 0x3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    dist[k] = 0;
    for(int i=0;i<n;i++){
        int t = -1;
        for(int j=0;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])){
                t = j;
            }
        }
        st[t] = 1;
        for(int j=0;j<=n;j++){
            if(L[j]>=minL&&L[j]<=maxL){
                dist[j] = min(dist[j], dist[t]+g[t][j]);
            }
        }
    }
}

int main(){
    scanf("%d%d", &m, &n);
    memset(g, 0x3f, sizeof(g));
    for(int i=1;i<=n;i++){
        int p, x;
        scanf("%d%d%d", &p, &L[i], &x);
        g[0][i] = p;
        while(x--){
            int t, v;
            scanf("%d%d", &t, &v);
            g[t][i] = v;
        }
    }
    int res = 0x3f3f3f3f;
    for(int i=max(1, L[1]-m);i<=L[1];i++){
        minL = i;
        maxL = i+m;
        dijkstra(0);
        res = min(res, dist[1]);
    }
    cout << res << endl;
    return 0;
}

活动打卡代码 AcWing 1488. 最短距离(每日一题）

CODE_HUNTER
13小时前

点的集合到其他点的最短路径问题 —— 建立一个虚拟源点，虚拟源点到点的集合内的各点都存在一条边权为0的边
太妙了，这个技巧要狠狠记住！

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

typedef pair<int, int> PII;
const int N = 100010;
int h[N], e[3*N], w[3*N], ne[3*N], idx = 1;
int dist[N], st[N];
int n, m;

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

int dijkstra(int k){
    memset(dist, 0x3f3f3f3f, sizeof(dist));
    memset(st, 0, sizeof(st));
    priority_queue<PII, vector<PII>, greater<PII>> heak;
    dist[k] = 0;
    heak.push({0, k});
    while(heak.size()){
        int a = heak.top().second;
        heak.pop();
        if(st[a]) continue;
        st[a] = 1;
        for(int i=h[a];i;i=ne[i]){
            int b = e[i];
            dist[b] = min(dist[b], dist[a]+w[i]);
            if(!st[b]){
                heak.push({dist[b], b});
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    int k;
    scanf("%d", &k);
    while(k--){
        int t;
        scanf("%d", &t);
        add(0, t, 0);
    }
    dijkstra(0);
    int q;
    scanf("%d", &q);
    while(q--){
        int k;
        scanf("%d", &k);
        printf("%d\n", dist[k]);
    }
    return 0;
}

活动打卡代码 AcWing 850. Dijkstra求最短路 II（算法基础课）

CODE_HUNTER
14小时前

堆优化的dijkstra
堆优化选取dist最小点的过程

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

typedef pair<int, int> PII;
const int N = 150010;
int h[N], e[N], w[N], ne[N], idx = 1;
int st[N], dist[N];
int n, m;

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

int dijkstra(int k){
    memset(dist, 0x3f, sizeof(dist));
    dist[k] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heak;
    heak.push({dist[k], k});
    while(heak.size()){
        int a = heak.top().second;
        heak.pop();
        if(st[a]) continue;
        st[a] = 1;
        for(int i=h[a];i;i=ne[i]){
            int b = e[i];
            dist[b] = min(dist[b], dist[a]+w[i]);
            if(!st[b]){
                heak.push({dist[b], b});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main(){
    scanf("%d%d", &n, &m);
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    cout << dijkstra(1) << endl;
    return 0;
}

活动打卡代码 AcWing 849. Dijkstra求最短路 I（算法基础课）

CODE_HUNTER
14小时前

dijkstra 模板

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

const int N = 510;
int g[N][N];
int dist[N], st[N];
int n, m;

int dijkstra(int k){
    memset(dist, 0x3f, sizeof(dist));
    dist[k] = 0;
    for(int i=0;i<n;i++){
        int t = -1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[j]<dist[t])){
                t = j;
            }
        }
        st[t] = 1;
        for(int j=1;j<=n;j++){
            dist[j] = min(dist[j], dist[t]+g[t][j]);
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    else return dist[n];
}

int main(){
    scanf("%d%d", &n, &m);
    memset(g, 0x3f, sizeof(g));
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        if(g[a][b]>c) g[a][b] = c;
    }
    cout << dijkstra(1) << endl;
    return 0;
}

活动打卡代码 AcWing 456. 车站分级（算法提高课）

CODE_HUNTER
1天前

拓扑排序 + 图的中间点存储方式降低复杂度（$O(n*m) \rightarrow O(n+m)$）
暴力复杂度$O(n*m^2)$会TLE，使用中间点存储先拓扑后求路径的方式复杂度$O((n+m)*m)$

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

const int N = 2010, M = 1000010;
int h[N], e[M], ne[M], w[M], idx = 1;
int q[N], d[N], dist[N];
int st[N];
int n, m;

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

void toposort(){
    int head = 0, rear = 0;
    for(int i=1;i<=n+m;i++){
        if(!d[i]){
            q[rear++] = i;
        }
    }
    while(head<rear){
        int a = q[head++];
        for(int i=h[a];i;i=ne[i]){
            int b = e[i];
            d[b] --;
            if(!d[b]){
                q[rear++] = b;
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++){
        int s;
        scanf("%d", &s);
        memset(st, 0, sizeof(st));
        int start, end;
        for(int j=0;j<s;j++){
            int t;
            scanf("%d", &t);
            st[t] = 1;
            add(t, n+i, 0);
            if(j==0) start = t;
            if(j==s-1) end = t;
        }
        for(int j=start;j<=end;j++){
            if(!st[j]){
                add(n+i, j, 1);
            }
        }
    }
    toposort();
    for(int i=0;i<n+m;i++){
        int a = q[i];
        for(int j=h[a];j;j=ne[j]){
            int b = e[j];
            dist[b] = max(dist[b], dist[a]+w[j]);
        }
    }
    int res = 0;
    for(int i=1;i<=n;i++){
        res = max(res, dist[i]);
    }
    cout << res+1 << endl;
    return 0;
}

活动打卡代码 AcWing 1191. 家谱树（算法提高课）

CODE_HUNTER
1天前

简单的拓扑排序

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

const int N = 110;
int h[N], e[2*N], ne[2*N], idx;
int d[N];
int n;

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

void toposort(){
    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!d[i]) q.push(i);
    }
    while(!q.empty()){
        int a = q.front();
        printf("%d ", a);
        q.pop();
        for(int i=h[a];i!=-1;i=ne[i]){
            int b = e[i];
            d[b] --;
            if(!d[b]){
                q.push(b);
            }
        }
    }
}

int main(){
    scanf("%d", &n);
    memset(h, -1, sizeof(h));
    for(int i=1;i<=n;i++){
        while(1){
            int j;
            scanf("%d", &j);
            if(!j) break;
            add(i, j);
            d[j] ++;
        }
    }
    toposort();
    return 0;
}

用于日后记录一些我翻到的大佬们的优质博客/题解，冲！

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论

0 评论