拓扑排序

时间复杂度为O(n + m)

int topo_sort(){
    int hh = 0, tt = -1;

    //deg[i]为该点的入度
    for(int i = 1; i <= n; i++)
        if(deg[i] == 0) q[++tt] = i;


    while(hh <= tt){
        int t = q[hh++];
        ans.push_back(t);
        for(int i = head[t]; i; i = ne[i]){
            int y = ver[i];
            if(--deg[y] == 0){
                q[++tt] = y;
            }
        }
    }
    return tt == n - 1;
}

朴素版dijkstra算法

int g[N][N];
int n, m;
int d[N];
bool v[N];

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

堆优化版Dijkstra

int head[N], ver[N], edge[N], ne[N], tot;
int n, m;
int d[N];
bool v[N];

void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, ne[tot] = head[x], head[x] = tot;
}

int dijkstra(){
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    while(q.size()){
        auto x = q.top().second; q.pop();
        if(v[x]) continue;
        v[x] = 1;
        for(int i = head[x]; i; i = ne[i]){
            int y = ver[i], z = edge[i]; 
            if(v[y]) continue;
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                q.push({d[y], y});
            }
        }
    }
    if(d[n] == 0x3f3f3f3f) return -1;
    else return d[n];
}

bellman_ford 求有边数限制的最短路

struct Edge{
    int x, y, z;
}edges[M];

int d[N], backup[N];
int n, m, k;

bool bellman_ford(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int i = 0; i < k; i++){
        memcpy(backup, d, sizeof d);
        for(int j = 0; j < m; j++){
            int x = edges[j].x, y = edges[j].y, z = edges[j].z;
            d[y] = min(d[y], backup[x] + z);
        }
    }
    if(d[n] > 0x3f3f3f3f / 2) return false;
    else return true;
}

spfa求最短路

时间复杂度 平均情况下 O(m)，最坏情况下 O(nm), n 表示点数，m表示边数

int head[N], ver[N], edge[N], ne[N], tot;
bool v[N];
int d[N];

void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, ne[tot] = head[x], head[x] = tot;
}

bool spfa(){
    memset(d, 0x3f, sizeof d);
    memset(v, 0, sizeof v);
    d[1] = 0; v[1] = 1;
    queue<int> q;
    q.push(1);
    while(q.size()){
        int x = q.front(); q.pop();
        v[x] = 0;
        for(int i = head[x]; i; i = ne[i]){
            int y = ver[i], z = edge[i];
            if(d[y] > d[x] + z){
                d[y] = d[x] + z;
                if(!v[y]) q.push(y), v[y] = 1;
            }
        }
    }
    if(d[n] == 0x3f3f3f3f) return false;
    else return true;
}

spfa判断负环

int head[N], ver[N], edge[N], ne[N], tot;

int n, m;
bool v[N];
int d[N], cnt[N];

void add(int x, int y, int z){
    ver[++tot] = y, edge[tot] = z, ne[tot] = head[x], head[x] = tot;

}

int spfa(){  
    queue<int> q;
    for(int i = 1; i <= n; i++){
        v[i] = 1;
        q.push(i);
    }

    while(q.size()){
        int t = q.front();
        q.pop();

        v[t] = false;

        for(int i = head[t]; i; i = ne[i]){
            int y = ver[i], z = edge[i];
            if(d[y] > d[t] + z){
                cnt[y] = cnt[t] + 1;
                d[y] = d[t] + z;
                if(cnt[y] >= n) return true;
                if(!v[y]) {
                    q.push(y);
                    v[y] = true;
                }
            }
        }
    }
    return false;
}