一道综合性很强的题。
有负权无负环的单源最短路：拓扑排序（所有正权连通块间） + Dijkstra（每个正权连通块内）
DFS求出所有连通块，拓扑排序按照块的拓扑序计算最短距离，遍历到该块时块内执行Dijkstra求出该块内所有点的最短距离，若更新时遇到不属于该块的点，则处理连通块的入度并判断是否将它所在的连通块入队。
关于SPFA，他死了。。。

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

typedef pair<int, int> PII;
const int N = 25010, M = 150010;
int h[N], e[M], w[M], ne[M], idx = 1;
int dist[N], st[N];
int id[N];
vector<int> block[N];
int d[N];
int bcnt;
queue<int> q;
int n, P, R, s;

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

void dfs(int a, int bid){
    id[a] = bid;
    block[bid].push_back(a);
    for(int i=h[a];i;i=ne[i]){
        int b = e[i];
        if(!id[b]) dfs(b, bid);
    }
}

void dijkstra(int t){
    priority_queue<PII, vector<PII>, greater<PII>> heak;
    for(auto it: block[t]){
        heak.push({dist[it], it});
    }
    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(id[b]==t){
                heak.push({dist[b], b});
            }
            else{
                d[id[b]] --;
                if(!d[id[b]]) q.push(id[b]);
            }
        }
    }
}

void toposort(){
    memset(dist, 0x3f, sizeof(dist));
    dist[s] = 0;
    for(int i=1;i<=bcnt;i++){
        if(!d[i]){
            q.push(i);
        }
    }
    while(q.size()){
        int t = q.front();
        q.pop();
        dijkstra(t);
    }
}

int main(){
    scanf("%d%d%d%d", &n, &P, &R, &s);
    while(P--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }
    for(int i=1;i<=n;i++){
        if(!id[i]) dfs(i, ++bcnt);
    }
    while(R--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        d[id[b]] ++;
    }
    toposort();
    for(int i=1;i<=n;i++){
        if(dist[i]>0x3f3f3f3f/2) printf("NO PATH\n");
        else printf("%d\n", dist[i]);
    }
    return 0;
}

Kruskal 模板

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

typedef pair<int, pair<int, int>> PIII;
const int N = 210;
int p[N];
PIII e[N];
int n, k;

int find(int a){
    if(p[a]!=a) p[a] = find(p[a]);
    return p[a];
}

int kruskal(){
    int res = 0;
    sort(e, e+k);
    for(int i=0;i<k;i++){
        int c = e[i].first;
        int a = e[i].second.first, b = e[i].second.second;
        int x = find(a), y = find(b);
        if(x!=y){
            p[x] = y;
            res += c;
        }
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i=1;i<=n;i++) p[i] = i;
    int sum = 0;
    for(int i=0;i<k;i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        e[i] = {c, {a, b}};
        sum += c;
    }
    cout << sum-kruskal() << endl;
    return 0;
}

Prim 模板

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

const int N = 110;
int g[N][N], dist[N];
int st[N];
int n, res;

void prim(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 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;
        res += dist[t];
        for(int j=1;j<=n;j++){
            if(!st[j]){
                dist[j] = min(dist[j], g[t][j]);
            }
        }
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d", &g[i][j]);
        }
    }
    prim();
    cout << res << endl;
    return 0;
}

Kruskal 模板

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

typedef pair<int, pair<int, int>> PIII;
const int N = 200010;
int p[N];
PIII e[N];
int n, m;
int res;

int find(int a){
    if(p[a]!=a) p[a] = find(p[a]);
    return p[a];
}

bool kruskal(){
    sort(e, e+m);
    int cnt = 0;
    for(int i=0;i<m;i++){
        int c = e[i].first;
        int a = e[i].second.first, b = e[i].second.second;
        int x = find(a), y = find(b);
        if(x!=y){
            p[x] = y;
            res += c;
            cnt ++;
        }
    }
    return cnt==n-1;
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) p[i] = i;
    for(int i=0;i<m;i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        e[i] = {c, {a, b}};
    }
    if(kruskal()) printf("%d\n", res);
    else printf("impossible\n");
    return 0;
}

Prim 模板
两种求最小生成树的方法：

• Prim：逐点加入，并更新集合外各点到点集合的距离（整体过程类似Dijkstra） 适用于稠密图
• Kruskal：边按边权大小排序，逐边加入，并利用并查集维护点集合 适用于稀疏图

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

const int N = 510, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
int st[N];
int n, m;
int res;

bool prim(){
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    for(int i=0;i<n;i++){
        int t = -1;
        for(int j=1;j<=n;j++){
            if(!st[j]&&(t==-1||dist[t]>dist[j])){
                t = j;
            }
        }
        if(dist[t]>INF/2) return false;
        st[t] = 1;
        res += dist[t];
        for(int j=1;j<=n;j++){
            if(!st[j]){
                dist[j] = min(dist[j], g[t][j]);
            }
        }
    }
    return true;
}

int main(){
    scanf("%d%d", &n, &m);
    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] = g[b][a] = min(g[a][b], c);
    }
    if(prim()) printf("%d\n", res);
    else printf("impossible\n");
    return 0;
}

这是第一次我做出来的图论题555~
Floyd求多源最短路，并统计dmax[i]（记录其他点到i点的最大距离），并求出连接前的最大半径res。遍历邻接矩阵，将不连通的两点i，j连接并计算连接后的新牧场的最大半径 —— dmax[i]+dmax[j]+distance(i, j)，由该值和res可得每种情况连接后的最大半径，根据统计即可得知最小化的最大半径值。

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

const int N = 160, INF = 1e8;
int x[N], y[N];
double g[N][N];
double dmax[N]; //记录其他点到i点的最大距离
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(){
    scanf("%d", &n);
    for(int i=1;i<=n;i++){
        scanf("%d%d", &x[i], &y[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int t;
            scanf("%1d", &t);
            if(t){
                double xx = x[i]-x[j];
                double yy = y[i]-y[j];
                g[i][j] = sqrt(xx*xx+yy*yy);
            }
            else if(i==j) g[i][j] = 0;
            else g[i][j] = INF;
        }
    }
    floyd();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(g[i][j]<INF-10){
                dmax[j] = max(dmax[j], g[i][j]);
            }
        }
    }
    double res = 0;
    for(int i=1;i<=n;i++) res = max(res, dmax[i]);
    double ans = INF;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(g[i][j]>INF-10){
                double xx = x[i]-x[j];
                double yy = y[i]-y[j];
                ans = min(ans, max(res, dmax[i]+dmax[j]+sqrt(xx*xx+yy*yy)));
            }
        }
    }
    printf("%.6lf\n", ans);
    return 0;
}

在i点之前购买并在i点之后出售的收益 $=$ 在i点之后出售的最高价格dmax $-$ 在i点之前购买的最低价格dmin
故计算所有点的dmin和dmax，即可求出最大的收益。
正向建图 + 反向建图 + 以SPFA的方式计算“最短路”（dmin/dmax）
本题使用SPFA的原因：由于使用i点更新其他点时，i点的“最短距离”并未确定，这一点与Dijkstra算法不符。通常，SPFA比Dijkstra的适用范围更广。

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

const int N = 100010, M = 1000010;
int hf[N], hb[N], e[M], ne[M], idx = 1;
int w[N];
int st[N];
int dmin[N], dmax[N];
int n, m;

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

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

void spfab(){
    memset(st, 0, sizeof(st));
    memset(dmax, 0xc0, sizeof(dmax));
    dmax[n] = w[n];
    queue<int> q;
    q.push(n);
    st[n] = 1;
    while(q.size()){
        int a = q.front();
        q.pop();
        st[a] = 0;
        for(int i=hb[a];i;i=ne[i]){
            int b = e[i];
            if(dmax[b]<max(w[b], dmax[a])){
                dmax[b] = max(w[b], dmax[a]);
                if(!st[b]){
                    q.push(b);
                    st[b] = 1;
                }
            }
        }
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1;i<=n;i++) scanf("%d", &w[i]);
    while(m--){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(hf, a, b);
        add(hb, b, a);
        if(c==2){
            add(hf, b, a);
            add(hb, a, b);
        }
    }
    spfaf();
    spfab();
    int res = 0;
    for(int i=1;i<=n;i++) res = max(res, dmax[i]-dmin[i]);
    cout << res << endl;
    return 0;
}

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

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

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;
}

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;
}