题解 P3385 [模板]负环

发表于 | 更新于 | 分类于 | 阅读次数：

题面

来一篇能过的题解

如楼下某大佬所说，spfa的复杂度也是$O(nm)$,所以只要用常数更小的$Bellman-ford$即可。

然而，图不一定联通，因此只要加一个虚拟节点，从该节点向其余每个点连一条单向边，权值任意。显然，原图若存在负环，新图也存在，反之，原图若不存在负环，则新图也不存在。因此直接跑一遍即可。
让我们思考这个过程：这个过程又可等价给每个点一个任意的初始距离(即从虚拟节点连向该点的边权)
为什么要卡常???不加inline更快(逃

上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
int dis[2010],u[3010],v[3010],w[3010];
void Bellman_Ford(int n,int m){//bellman-ford除初始化的板子
                                      //并不需要初始化
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&u[i],&v[i],&w[i]);
    for(int k=1;k<=n;k++){
        int check=1;
        for(int i=1;i<=m;i++){
            if(dis[v[i]]>dis[u[i]]+w[i])
                dis[v[i]]=dis[u[i]]+w[i],check=0;
            if(w[i]>=0 && dis[u[i]]>dis[v[i]]+w[i])//之前大佬的代码在这里挂了
                dis[u[i]]=dis[v[i]]+w[i],check=0;
        }
        if(check) break;
    }
    for(int i=1;i<=m;i++){
        if(dis[v[i]]>dis[u[i]]+w[i]){
            printf("YE5\n");
            return;
        }
        if(w[i]>=0 && dis[u[i]]>dis[v[i]]+w[i]){//当然还有这里
            printf("YE5\n");
            return;
        }
    }
    printf("N0\n");
}
int main(){
    int t,n,m;
    scanf("%d",&t);
    while(t--)
        scanf("%d%d",&n,&m),Bellman_Ford(n,m);
}