P3385

Aryper · 2020-06-26 16:40:13 · 个人记录

负环

模板题。但是我已经修改过好几次了。。。人们对负环尚未有完全正确的理解。。。

判断入队次数而非松弛次数。如果入队次数 \ge n 说明有负环。

然后写一个另一种方法：设 cnt_x 为 1 到 x 的最短路上包含的边数，然后每次松弛的时候 cnt_y=cnt_x+1 。然后如果有 cnt_x\ge n ，说明有负环。否则算法可正常运行至结束。

这两种方法可以同时使用。

第三种是 dfs 的 spfa 。虽然效率确实高一点，但是一般到了判负环这个地步，卡这个东西第一个没意思，第二个这种方法会使不存在负环时的效率显著降低，而且求最短路的效率也会降低。。。只要数据精心构造，不存在负环的情况可以把这个方法卡至指数级别。。。然后栈优化也是如此，，反正不是特殊情况的话用起来会非常危险。。。

但是出于实践精神的考量我去写了一遍 dfs 版，发现它被第九个点卡掉了。。。

然后是有关赋 0 的问题。。这个题不能初值赋 0 ，原因是它的起始点是 1 ，而不是任意节点。

那么关于为什么任意节点出发这个初值就能赋 0 ，下面给一个证明：

证明上述结论，即证明在负环中一定存在一个节点，它从自身走到自身这个负环的过程中，权值一直是负的。

设有点 s 在这个负环上，设从 s 走到 t 时权值最大，那么 t 也在负环上。

假设从 t 再走到 s 的过程中，若存在 p ，使得 t\rightarrow p 权值为正，那么从 s\rightarrow p 的权值大于 s\rightarrow t 的权值，与假设相反，故矛盾。所以从 t\rightarrow s 的权值始终为负。

设 t\rightarrow s 的权值为 a ，s\rightarrow t 的权值为 b ，则根据负环定义，a+b<0 ，则 b<-a 。

根据假设，因为 b 是最大正权值，则在 s\rightarrow t 的过程中，若产生权值 c ，则必有 c<b ，则必有 c<b<-a ，则必有 a+c<0 。所以从 t\rightarrow s\rightarrow t 的过程中权值始终为负，证毕。

代码（双管齐下）：

#include<iostream>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;

const ll N=6e3,M=6e3,inf=(1ll<<31)-1;

ll n,m,u,v,w,h,tot,T;

ll f[N+6],head[N+5],ver[M*2+5],nxt[M*2+5],wt[M*2+5];

ll cnt[N+5],in[N+5];

bool vis[N+5];

queue<ll> q;

bool SPFA(ll s) {
    for(ll i=1;i<=n;i++) f[i]=inf;
    f[s]=0;q.push(s);vis[s]=1;in[s]++;
    while(!q.empty()) {
        h=q.front();q.pop();vis[h]=0;
        for(ll i=head[h];i;i=nxt[i]) {
            if(f[ver[i]]>f[h]+wt[i]) {
                f[ver[i]]=f[h]+wt[i];
                cnt[ver[i]]=cnt[h]+1;
                if(cnt[ver[i]]>=n) return 1;
                if(!vis[ver[i]]) {
                    in[ver[i]]++;
                    if(in[ver[i]]>=n) return 1;
                    q.push(ver[i]);vis[ver[i]]=1;
                }
            }
        }
    }
    return 0;
}

void add(ll u,ll v,ll w) {
    ver[++tot]=v;wt[tot]=w;
    nxt[tot]=head[u];head[u]=tot;
}

void init() {
    while(!q.empty()) q.pop();
    for(ll i=1;i<=n;i++) {
        cnt[i]=0;in[i]=0;vis[i]=0;
    }
    for(ll i=1;i<=tot;i++) {
        ver[i]=0;wt[i]=0;nxt[i]=0;head[i]=0;
    }
    tot=0;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {
        do{buf[++len]=x%10+48;x/=10;}while(x);
    }
    else {
        putchar('-');
        do{buf[++len]=-(x%10)+48;x/=10;}while(x);
    }
    while(len>=0) putchar(buf[len--]);
}

void writeln(ll x) {
    write(x);putchar('\n');
}

int main() {

    T=read();

    while(T--) {
        init();
        n=read();m=read();
        for(ll i=1;i<=m;i++) {
            u=read();v=read();w=read();
            add(u,v,w);
            if(w>=0) add(v,u,w);
        }
        if(SPFA(1)) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

代码（判最短路上包含边数法）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const ll N=6e3;

ll n,m,u,v,w,flg,T,tot,h;

ll vis[N+5],ver[N*2+5],wt[N*2+5],nxt[N*2+5],head[N+5],f[N+5],cnt[N+5];

queue<ll> q;

void spfa(ll s) {
    memset(f,0x3f,sizeof(f));
    f[s]=0;q.push(s);
    while(!q.empty()) {
        h=q.front();q.pop();vis[h]=0;
        for(ll i=head[h];i;i=nxt[i]) {
            if(f[ver[i]]>f[h]+wt[i]) {
                f[ver[i]]=f[h]+wt[i];cnt[ver[i]]=cnt[h]+1;
                if(cnt[ver[i]]>=n) {
                    flg=1;break;
                }
                if(!vis[ver[i]]) {
                    vis[ver[i]]=1;q.push(ver[i]);
                }
            }
        }
        if(flg) break;
    }
}

void add(ll u,ll v,ll w) {
    ver[++tot]=v;wt[tot]=w;
    nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    T=read();

    while(T--) {
        memset(vis,0,sizeof(vis));
        memset(ver,0,sizeof(ver));
        memset(wt,0,sizeof(wt));
        memset(nxt,0,sizeof(nxt));
        memset(head,0,sizeof(head));
        memset(cnt,0,sizeof(cnt));
        while(!q.empty()) q.pop();
        tot=0;flg=0;
        n=read();m=read();
        for(ll i=1;i<=m;i++) {
            u=read();v=read();w=read();
            add(u,v,w);
            if(w>=0) add(v,u,w);
        }
        spfa(1);
        if(flg) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}

代码（ dfs 版）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const ll N=6e3;

ll n,m,u,v,w,flg,T,tot;

ll vis[N+5],ver[N*2+5],wt[N*2+5],nxt[N*2+5],head[N+5],f[N+5];

void dfs(ll s) {
    vis[s]=1;
    for(ll i=head[s];i;i=nxt[i]) {
        if(f[ver[i]]>f[s]+wt[i]) {
            f[ver[i]]=f[s]+wt[i];
            if(vis[ver[i]]||flg) {
                flg=1;break;
            }
            dfs(ver[i]);
        }
    }
    vis[s]=0;
}

void add(ll u,ll v,ll w) {
    ver[++tot]=v;wt[tot]=w;
    nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    T=read();

    while(T--) {
        memset(vis,0,sizeof(vis));
        memset(ver,0,sizeof(ver));
        memset(wt,0,sizeof(wt));
        memset(nxt,0,sizeof(nxt));
        memset(head,0,sizeof(head));
        memset(f,0x3f,sizeof(f));
        tot=0;flg=0;
        n=read();m=read();
        for(ll i=1;i<=m;i++) {
            u=read();v=read();w=read();
            add(u,v,w);
            if(w>=0) add(v,u,w);
        }
        f[1]=0;
        dfs(1);
        if(flg) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}