ConanKIDの小窝

ConanKIDの小窝

负环 学习笔记

posted on 2020-12-26 16:24:40 | under 学习笔记 |

1. 引入

负环,即边权之和为负数的环。

大家试想,在求最短路时,如果图上存在负环,那么我就可以一直绕着这个环走无限多圈,路径的边权之和就会变得无限小,求最短路也就毫无意义。

因此,判断一张图上是否存在负环也就成了一个比较重要的问题。

接下来,本人将会介绍两种方法。

2. 从点的角度入手,判断负环是否存在

考虑SPFA算法的过程。

SPFA算法基于如下推论:若图中不存在负环,那么$n-1$次松弛以后,最短路应该就求完了。

因此,每个点至多被松弛$n-1$次。

但是负环会导致每个点被无限松弛。所以,统计一下每个点被松弛的次数$tot$,只要$tot_i\ge n$,则说明存在负环。

但是,这种算法可能会被$\operatorname{Hack}$。如果图中存在重边,即有两条从$u$指向$v$的边,就可能导致$v$被$u$松弛两次,得出错误的结果。

虽然概率很小,但这种情况还是有可能发生的。

所以,本人更喜欢的是下面一种方法。

3. 从边的角度入手,判断负环是否存在

定义$tot_i$表示源点到$i$的最短路经过的边的数量。

如果不存在负环,那么在走最短路时,每个点至多经过一次。所以,$tot$应该均不大于$n-1$。

那么只要在SPFA的过程中,发现任意一个$tot_i \ge n$,则存在负环。

而$tot$数组只要在松弛的时候更新一下就好了。

bool spfa(){
    memset(p,0,sizeof(p));
    memset(tot,0,sizeof(tot));
    for(int i=1;i<=n;i++)
        dis[i]=1e9;
    dis[1]=0;
    queue<int>q;
    q.push(1);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        p[u]=0;
        for(int i=head[u];i;i=a[i].next){
            int v=a[i].y;
            if(dis[v]>dis[u]+a[i].w){
                dis[v]=dis[u]+a[i].w;
                tot[v]=tot[u]+1;
                if(tot[v]>=n)return 1;
                if(!p[v]){
                    q.push(v);
                    p[v]=1;
                }
            }
        }
    }
    return 0;
}

我们发现,这种算法就不受重边的影响,可以更好的解决问题。

以上两种方法时间复杂度均为$O(nm)$。

4. 应用

UVA11090

考虑二分答案。那么问题转化为,判定图中是否存在边的平均值小于等于$mid$的环。

那么开始愉快的颓式子吧。

若环中共有$k$条边,第$i$条的边权为$s_i$,那么

$\because \dfrac{\sum_{i=1}^m s_i}{m}\le mid$

$\therefore \sum_{i=1}^m s_i -mid\times m\le 0$

$\therefore \sum_{i=1}^m (s_i-mid)\le 0$

所以我们可以再建一张新图,若原图边权为$w$,则新图边权为$w-mid$。这时,问题就转化为判断图上是否存在负环了。

于是乎,问题迎刃而解。

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-4;
int t;
int n,m;
double s;
int head[1005],cnt; 
struct node{
    int x,y,next;
    double w;
}a[5005],b[5005];
double dis[1005];
bool p[1005];
int tot[1005];
void add(int x,int y,double w){
    cnt++;
    a[cnt].x=x; a[cnt].y=y; a[cnt].w=w;
    a[cnt].next=head[x];
    head[x]=cnt;
} 
void init(){
    cin>>n>>m;
    cnt=0;
    memset(head,0,sizeof(head));
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
}
bool spfa(){//spfa判负环
    memset(p,0,sizeof(p));
    memset(tot,0,sizeof(tot));
    for(int i=1;i<=n;i++)
        dis[i]=1e9;
    dis[1]=0;
    queue<int>q;
    for(int i=1;i<=n;i++){
        q.push(i);
        p[i]=1;
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        p[u]=0;
        for(int i=head[u];i;i=a[i].next){
            int v=a[i].y;
            if(dis[v]>dis[u]+a[i].w){
                dis[v]=dis[u]+a[i].w;
                tot[v]=tot[u]+1;
                if(tot[v]>=n)return 1;
                if(!p[v]){
                    q.push(v);
                    p[v]=1;
                }
            }
        }
    }
    return 0;
}
bool check(double mid){
    for(int i=1;i<=m;i++){
        b[i]=a[i];
        a[i].w=a[i].w-mid;//建新图
    }
    bool fl=spfa();
    for(int i=1;i<=m;i++)
        a[i]=b[i];
    return fl;
}
double dss(){//实数域二分求解
    double l=-eps,r=1e7+eps;
    while(l+eps<r){
        double mid=(l+r)/2.;
        if(check(mid))r=mid;
        else l=mid;
    }
    if(r!=1e7+eps)return r;
    return -1;//注意这里要判断是否存在回路
}
void work(int d){
    init();
    double ans=dss();
    if(ans==-1)printf("Case #%d: No cycle found.\n",d);
    else printf("Case #%d: %.2lf\n",d,ans);
}
int main(){
    cin>>t;
    for(int i=1;i<=t;i++)
        work(i);
    return 0;
}

完结撒花