超级源点/汇点(算法篇)

算法之超级源点/汇点

超级源点/汇点

概念：

• 超级源点/汇点是模拟出来的虚拟点，多用于图中：

  1. 同时有多个源点和多个汇点，建立超级源点和超级汇点
  2. 同时有多个源点和一个汇点，建立超级源点
  3. 同时有多个汇点和一个源点，建立超级汇点

  总结：源点和汇点哪个有多个，就开哪个的超级点

• 介绍：我们平时所做的算法多是适用于一个源点到一个汇点或者是一个源点到多个汇点的类型，但是如果出现多个源点对应多个汇点时，我们会不知所措。跑多遍算法？那样会TLE，换个思维，既然是从多个源点出发到多个汇点，我们能不能建立一个点来代替多个源点/汇点 的效果，而又不影响答案。

做法：

• 当我们具有多个源点和一个汇点，我们要求源点到汇点的最短路径，则可以建立一个超级源点，连接所有源点，并且路径长度为0，然后只需要跑超级源点到汇点这(n+1)个点的最短距离即可

例题：

ACWing 1488.最短距离

分析：

要求每次查询给出的村庄y到最近距离的商店的距离，对于每次查询，起点只有一个，汇点有多个，我们可以逆向思维，这样就变成商店作为源点，村庄y作为汇点，就变成了多个源点到单个汇点问题，这样我们创建一个超级源点，连接所有源点，并且路径长度为0，去跑dijkstra算法即可

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

struct pii{
    int v,w;
};

struct edge{
    int d,u;
    bool operator>(const edge& other) const{
        return d>other.d;
    }
};


const int N=3e5+20;
const int INF=0x3f3f3f3f;
int n,m,k,q,a,b,c;
int dist[N];
bool vis[N];
vector<pii>g[N];

void dijkstra(){
    memset(dist,INF,sizeof dist);
    dist[0]=0;
    priority_queue<edge,vector<edge>,greater<edge>>pq;
    pq.push({0,0});
    while(!pq.empty()){
        edge p=pq.top();
        pq.pop();
        int u=p.u,d=p.d;
        if(vis[u]) continue;
        vis[u]=1;
        for(auto x:g[u]){
            int v=x.v,w=x.w;
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                pq.push({dist[v],v});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    cin>>n>>m;
    while(m--){
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    cin>>k;
    while(k--){
        cin>>a;
        g[0].push_back({a,0});
    }
    dijkstra();
    cin>>q;
    while(q--){
        cin>>a;
        cout<<dist[a]<<endl;
    }
    system("pause");
    return 0;
}

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms