|
试题描述
|
|
输入数据给出一个有 N 个节点，M 条边的带权有向图。要求你写一个程序，判断这个有向图中是否存在负权回路。如果从一个点沿着某条路径出发，又回到了自己，而且所经过的边上的权和小于 0，就说这条路是一个负权回路。
如果存在负权回路，只输出一行 −1；如果不存在负权回路，再求出一个点S到每个点的最短路的长度。约定：S 到 S 的距离为 0，如果 S 与这个点不连通，则输出 NoPath。 |
|
输入
|
|
第一行三个正整数，分别为点数 N，边数 M，源点 S；
以下 M 行，每行三个整数 a,b,c，表示点 a,b之间连有一条边，权值为 c。 |
|
输出
|
|
如果存在负权环，只输出一行 −1，否则按以下格式输出：共 N 行，第 i 行描述 S 点到点 i 的最短路
如果 S 与 i 不连通，输出 NoPath； 如果 i=S，输出 0。 其他情况输出 S 到 i 的最短路的长度。 |
|
输入示例
|
|
6 8 1
1 3 4 1 2 6 3 4 -7 6 4 2 2 4 5 3 6 3 4 5 1 3 5 4 |
|
输出示例
|
|
0
6 4 -3 -2 |
先用DFS判断负环，然后跑最短路即可。
DFS具体判断负环的方法是：记录一个vis数组，表示在你这次搜索过程中有没有走到这个点，如果在搜索的时候，发现这个目标点vis==1了，并且你还可以更新这个目标点的dis，那么就存在负环。因为这就相当于你跑完一圈，dis又少了，那么这个环肯定是负的。
这里有一个优化：是大佬YSF、SYF和我们清华毕业的数学老师姚璐提出并证明的。一般判断负环时，我们会把dis初始值赋成INF，但是实际上，我们可以赋0。相当于DFS跑最短路的时候，遇到正边就不跑了，这样会节省很大的时间复杂度。那么怎么证明正确性呢？
首先，我们需要证明一点，对于一个负环，一定有一个点，从这个点到第起始点的所有边权都为负，因为如果有正的，dis为0的情况可能会被正的卡住。那么又怎么证明这个呢？
我们可以画一个函数图像，x坐标表示负环上的每个点，y表示到x点时经过的边权。画出来后，你会发现，一定有一个峰值，然后对于这个峰值建系，它右侧的值全都是负的了。
具体代码如下（注意我的dis赋成0也可以AC，也是一个上面说法的验证）：
#include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cstring> #include <queue> #define REP(i,k,n) for(int i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } int T; int flag=0; int n,m,s; int total=0,nxt[200010],head[200050],to[600510],val[605010]; int vis[200050],dis[100550],book[200050]; int q[1000010]; inline void adl(int a,int b,int c){ total++; to[total]=b; val[total]=c; nxt[total]=head[a]; head[a]=total; return ; } queue <int> Q; inline void dfs(int u){ book[u]=1; for(int e=head[u];e;e=nxt[e]){ if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; if(vis[to[e]]){ flag=1; return ; } if(flag) return ; vis[to[e]]=1; dfs(to[e]); vis[to[e]]=0; } } return ; } void SPFA(int st){ memset(vis,0,sizeof(vis)); memset(dis,127,sizeof(dis)); int hea=1,tail=1; //q[hea]=st; Q.push(st); dis[st]=0; while(!Q.empty()/*tail>=hea*/){ int u=Q.front(); //hea++; Q.pop(); vis[u]=0; for(int e=head[u];e;e=nxt[e]) if(dis[to[e]]>dis[u]+val[e]){ dis[to[e]]=dis[u]+val[e]; if(!vis[to[e]]){ vis[to[e]]=1; Q.push(to[e]); } } } return ; } int main() { total=flag=0; //memset(dis,127,sizeof(dis)); in(n);in(m);in(s); int a,b,c; REP(i,1,m){ in(a);in(b);in(c); adl(a,b,c); } REP(i,1,n) if(!book[i]){ memset(vis,0,sizeof(vis)); dfs(i); if(flag) break; } if(flag){ cout<<-1<<endl; return 0; } SPFA(s); REP(i,1,n) if(dis[i]>999999999) cout<<"NoPath"<<endl; else cout<<dis[i]<<endl; }