对于超级源点和超级汇点的理解

本文主要是介绍对于超级源点和超级汇点的理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

超级源点

适用情况：
对与一些题目当求任意多个起点的最短路时，使用floyd会超时，对每个起点都跑一次最短路也会超时

怎么用：
这时我们可以直接再建立一个点，给这个点建立指向每个起点的单向边(边权值都定义为0），这样就可以通过求以这个点的最短里来求所有起点的最短路了，这个点就叫超级源了

疑问：

那么这样求出来的最短路是不是真的最短路？新建立的边会不会给图带来环，导致算法出错呢？

图示：
在这里插入图片描述

对于第一个问题：

以超级源为起点求出来的是关于超级源的最短路这是毫无疑问的。但其它点关于超级源的最短路必须经过超级源与起点的单向边，不然就没有路径。所以只要有最短路就一定会经过题目要求的起点，而起点到超级源的边权是0。

所以

超级源到任意终点的最短路长度 =起点( 该终点的最短路所经过的）到终点的长度 + 超级源到起点的最短路（0）

所以

超级源到任意终点的最短路长度 = 起点( 该终点的最短路所经过的）到终点的长度；

如图超级源到T的距离 = 起点1 到 T的距离

对于第二个问题

看图可以知道，我们建立到起点的边是单向边，所以不用担心新建立的边会使图产生负环。

例题：
赚钱

思路，建立一个超级源，再建立超级源到其它点的单向0权边，把题目说的"路径 "的权值赋值为-D，把做飞机的边权值赋值为f(飞机票钱）- D
，这样用spfa求最短路即可，如果有负环，说明可以一直赚钱，就输出orz,如果没有负环，就输出 max(所有点的 abs(最短路)) + D,注意要+D是因为起点城市也可以赚钱，但建图边权是0，所以少算了起点城市赚的钱。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dist[320];//超级源国到每个点的距离
ll head[320];//链式前向星
ll ct[320];//判断是否有环
bool vis[320];//判断点是否已经在队列里
int D,P,C,F;struct point{int to,w,next;
}edge[1000];int cnt = 0;
void addedage(int x,int y,int z){edge[++cnt].to = y;edge[cnt].w = z;edge[cnt].next = head[x];head[x] = cnt;
}void spfa(void){dist[0] = 0;//以超级源为起点queue<int> q;q.push(0);vis[0] = true;while(!q.empty()){int t = q.front();q.pop();vis[t] = false;for(int i = head[t];~i;i = edge[i].next){int u = edge[i].to;if(dist[u] > dist[t] + edge[i].w){dist[u] = dist[t] + edge[i].w;if(!vis[u]){//不在队列里才入队q.push(u);vis[u] = true;if(ct[u]++ == C){//如果被优化次数等于n则说明有负环printf("orz\n");return ;}}}}}ll ans = 0;for(int i = 1;i <= C;i++){//cout << i << " " << dist[i] << endl;ans = min(ans,dist[i]);}printf("%lld\n",-ans + D);//少算了超级源到起点的那条边return ;
}
int main(){memset(dist,0x3f,sizeof(dist));memset(head,-1,sizeof(head));scanf("%d%d%d%d",&D,&P,&C,&F);int x,y,z = -D;for(int i = 0;i < P;i++){scanf("%d %d",&x,&y);addedage(x,y,z);}for(int i = 0;i < F;i++){scanf("%d %d %d",&x,&y,&z);addedage(x,y,z-D);}for(int i = 1;i <=C;i++){//加上超级源到任意起点的单向0权边addedage(0,i,0);}spfa();//system("pause");return 0;
}