圖論模闆（拓撲排序、最短路）

圖論模闆

• • 一、拓撲排序
  • • 題意
    • 代碼
  • 二、Dijkstra
  • • 題意
    • 代碼1（樸素版）
    • 代碼2（堆優化版）
  • 三、Bellman-Ford
  • • 題意
    • 代碼
  • 四、spfa
  • • 題意1（最短路）
    • 代碼1
    • 題意2（判負環）
    • 代碼2
  • 五、Floyd
  • • 題意
    • 代碼

一、拓撲排序

題意

輸出拓撲排序，如果不存在輸出-1.

代碼

void topsort()
{
    queue<int> que;
    for(int i=1;i<=n;i++)
        if(!din[i]) que.push(i), ans[++num] = i;
    
    while(que.size()){
        int t = que.front();
        que.pop();
        for(int i=h[t];~i;i=ne[i]){
            int j = e[i];
            if(--din[j]==0) que.push(j), ans[++num] = j;
        }
    }
    if(num<n){
        cout << -1;
        return;
    }
    for(int i=1;i<=num;i++) cout << ans[i] << ' ';
}
           

二、Dijkstra

題意

求單源最短路（不存在負邊權），不存在傳回-1

代碼1（樸素版）

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

代碼2（堆優化版）

int dijkstra()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    priority_queue<pii,vector<pii>,greater<pii>> heap;
    heap.push({0,1});
    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i=h[ver];~i;i=ne[i]){
            int j = e[i];
            if(dist[j]>distance+w[i]){
                dist[j] = distance + w[i];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[n]==0x3f3f3f3f) return -1;
    return dist[n];
}
           

三、Bellman-Ford

題意

存在負邊權的圖，邊數不超過 k k k的最短路

代碼

int n,m,k;
int dist[N];
int last[N];
struct Edge
{
    int a,b,c;
}edges[M];

void bellman_ford()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    for(int i=1;i<=k;i++){
        memcpy(last,dist,sizeof(dist));
        for(int j=0;j<m;j++){
            auto e = edges[j];
            dist[e.b] = min(dist[e.b], last[e.a] + e.c);
        }
    }
    if(dist[n]>0x3f3f3f3f/2) puts("impossible");
    else cout << dist[n] << endl;
}
           

四、spfa

題意1（最短路）

求帶負邊權的最短路

代碼1

int spfa()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    queue<int> que;
    que.push(1);
    st[1] = true;
    while(que.size()){
        int t = que.front();
        que.pop();
        st[t] = false;
        for(int i=h[t];~i;i=ne[i]){
            int j = e[i];
            if(dist[j]>dist[t]+w[i]){
                dist[j] = dist[t] + w[i];
                if(!st[j]){
                    que.push(j);
                    st[j] = true;
                }
            }
        }
    }
    return dist[n];
}
           

題意2（判負環）

判負環

代碼2

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

五、Floyd

題意

多源彙最短路

代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 210, inf = 0x3f3f3f3f;

int n,m,k;
int dist[N][N];

void floyd()
{
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}

int main()
{
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j) dist[i][j] = 0;
            else dist[i][j] = inf;
        }
    while(m--){
        int a,b,c;
        cin >> a >> b >> c;
        dist[a][b] = min(dist[a][b], c);
    }
    floyd();
    while(k--){
        int a,b;
        cin >> a >> b;
        int t = dist[a][b];
        if(t>inf/2) puts("impossible");
        else cout << t << endl;
    }
    return 0;
}