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

对于超级源点和超级汇点的理解超级源点 适用情况 对与一些题目当求任意多个起点的最短路时 使用 floyd 会超时 对每个起点都跑一次最短路也会超时 怎么用 这时我们可以直接再建立一个点 给这个点 建立指向每个起点的单向边 边权值都定义为 0 这样就可以通过求以这个点

大家好,我是讯享网,很高兴认识大家。

超级源点

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

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

疑问:

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



图示:
在这里插入图片描述
讯享网

对于第一个问题:

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

所以

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

所以

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

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

对于第二个问题

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

例题:
赚钱

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

讯享网

超级汇点

适用情况,怎么用:

就是题目要求当求多个终点,求其所有终点的最短路时,不用枚举这些终点了,直接建立一个点,再建立这些终点到这个超级汇点的0权单向边,最后跑个最短路,输出dist[T](T表示汇点,dist表示起点到汇点的距离)。

原理和超级源点一样,超级汇点和超级源点可以同时使用。

小讯
上一篇 2025-03-26 13:23
下一篇 2025-01-29 14:54

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/78985.html