【spfa判负环】虫洞

旧城等待， 2024-03-25 16:12 47阅读 0赞

[904. 虫洞 - AcWing题库][904. _ - AcWing]

题意：

![16ae3fe36bc9280302ace76f08afa4ed.png][]

思路：

其实就是让你看这个图里面存不存在负环

因为spfa每次跑一遍就至少更新一个点的dist，因此每个点最多被更新n次

所以可以维护每个点被更新的次数，如果被更新次数>=n，就说明存在

否则就说明不存在

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=5e2+10,mxe=3e3+10;
    struct ty{
        int to,next,w;
    }edge[mxe<<1];
    queue<int> q;
    int n,m1,m2,u,v,w,tot=0;
    int vis[mxn],head[mxn],dis[mxn],cnt[mxn];
    void add(int u,int v,int w){
        edge[tot].w=w;
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    bool spfa(){
        for(int i=1;i<=n;i++) q.push(i),vis[i]=1;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=0;
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]>dis[u]+edge[i].w){
                    dis[edge[i].to]=dis[u]+edge[i].w;
                    cnt[edge[i].to]=cnt[u]+1;
                    if(cnt[edge[i].to]>=n) return true;
                    if(!vis[edge[i].to]){
                        vis[edge[i].to]=1;
                        q.push(edge[i].to);
                    }
                }
            }
        }
        return false;
    }
    void init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            vis[i]=dis[i]=cnt[i]=0;
        }
        while(!q.empty()) q.pop();
    }
    void solve(){
        cin>>n>>m1>>m2;
        init();
        for(int i=1;i<=m1;i++){
            cin>>u>>v>>w;
            add(u,v,w);
            add(v,u,w);
        }
        for(int i=1;i<=m2;i++){
            cin>>u>>v>>w;
            add(u,v,-w);
        }
        if(spfa()) cout<<"YES"<<'\n';
        else cout<<"NO"<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int T=1;
        cin>>T;
        while(T--)solve();
        return 0;
    }

[904. _ - AcWing]: https://www.acwing.com/problem/content/906/
[16ae3fe36bc9280302ace76f08afa4ed.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5f225a18e07f48f0bede119636dec1c8.png