本文主要是介绍Holy Grail————计蒜客,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接
https://nanti.jisuanke.com/t/41305/
思路
题意是给一个n个点m条有向边的图,题目保证可能会存在负权边,不存在重边和自环,也不存在负环,然后给出六条边的起点u和终点v,题目保证在添加前不会有能从u到达v的路径。
每次添加都要保证:第一,按照题意,是要添加一条反向边将本来能从v到u的最短路变成权重为0(题目说花费,一个意思)。第二,添加之后不能有负环,第三,添加后的边会影响后面的添加。所以牵扯到负环那么本题自然采用SPFA算法(没用Bellman_Ford是因为第一复杂度不如SPFA,第二不习惯0.0),求出v到u的最短路后添加上负号即可。
为什么可以直接添加负号这里写一下我的证明想法,可能不太规范,如果搜到最短路是正的,那么直接在起终点添加一个负权边不会有负环,因为是它是所有路径的最小值且为正,那么就算取负号也不会影响其它路径成为负环;如果是负的同理,会找到所有路径的最小值且为负,那么这个负值取相反数之后就会比其它所有路径的绝对值都要大,那么它一定能让所有形成的环都变成正值;如果搜不到最短路,就代表存在负环,但是题目保证了初始图不存在负环,故这个情况不存在。
c++代码
#include<bits/stdc++.h>
using namespace std;const int INF=1e9+2;
const int N=310;int n,m;
int g[N][N];
int dis[N],vis[N];void SPFA(int u){memset(dis, INF, sizeof(dis));memset(vis,0,sizeof(vis));dis[u] = 0;vis[u] = 1;queue<int> q;q.push(u);while(q.size()){auto t=q.front();q.pop();vis[t]=0;for(int i=0;i<n;i++){if(dis[i]>dis[t]+g[t][i]){dis[i]=dis[t]+g[t][i];if(!vis[i]){vis[i]=1;q.push(i);}}}}
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);memset(g,INF,sizeof(g));for(int i=0;i<m;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);g[a][b]=c;}for(int i=0;i<6;i++){int u,v;scanf("%d%d",&u,&v);SPFA(v);g[u][v]=-dis[u];printf("%d\n",g[u][v]);}}return 0;
}
这篇关于Holy Grail————计蒜客的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!