[luogu3385]dfs_spfa判负环模板

解题关键：模板保存。

判负环不需要memset dis数组，因为已经更新过得d数组一定小于0，如果当前点可以更新d，说明d更小，有可能继续扩大负环，所以继续更新；如果比d[v]大，则不可能继续更新负环，所以直接终止。

 有向图只扫一个点貌似不可以。。。bfs_spfa的时候一定注意，但dfs_spfa一定可以。

dfs过不了这道题，因为必须经过1这个点，或许d不置0可以，但会超时？

有向图可以使用拓扑排序找环。

1、dfs

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<iostream>

#include<cmath>

#include<queue>

#define inf 0x3f3f3f3f

using namespace std;

const int inf=0x3f3f3f3f;

const int maxm=;

const int maxn=;

int head[maxn],tot,n,m;

struct edge{

    int to;

    int w;

    int nxt;

}e[maxm];

void add_edge(int u,int v,int w){

    e[tot].w=w;

    e[tot].to=v;

    e[tot].nxt=head[u];

    head[u]=tot++;

}

bool vis[maxn];

int d[maxn];

//

bool dfs_spfa(int u){

    vis[u]=;

    for(int i=head[u];i!=-;i=e[i].nxt){

        int v=e[i].to;

        if(d[v]>d[u]+e[i].w){

            d[v]=d[u]+e[i].w;

            if(vis[v]||dfs_spfa(v)) return ;

        }

    }

    vis[u]=;

    return ;

}

int main(){

    int a,b,c,T;

    scanf("%d",&T);

    while(T--){

        tot=;

        memset(head,-,sizeof head);

        memset(vis,,sizeof vis);

        memset(d,,sizeof d);

        scanf("%d%d",&n,&m);

        for(int i=;i<m;i++){//注意为双向边

            scanf("%d%d%d",&a,&b,&c);

            if(c<) add_edge(a,b,c);

            else add_edge(a,b,c),add_edge(b,a,c);

        }

        bool flag=false;

        for(int i=;i<=n;i++){

            if(dfs_spfa(i)){

                flag=true;

                break;

            }

        }

        if(flag) puts("YE5");

        else puts("N0");

    }

    return ;

}

2、bfs_spfa

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<iostream>

#include<cmath>

#include<queue>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxm=;

const int maxn=;

int head[maxn],tot,n,m,cnt[maxn],w;

struct edge{

    int to;

    int w;

    int nxt;

}e[maxm];

void add_edge(int u,int v,int w){

    e[tot].w=w;

    e[tot].to=v;

    e[tot].nxt=head[u];

    head[u]=tot++;

}

bool vis[maxn];

queue<int>que;//队列是点的队列

int d[maxn];

bool spfa(int s){

    memset(cnt,,sizeof cnt);

    fill(d+,d+n+,inf);

    memset(vis,,sizeof vis);

    while(!que.empty()) que.pop();

    que.push(s);

    vis[s]=true;

    d[s]=;

    while (!que.empty()){

        int u=que.front();

        que.pop();

        vis[u]=false;

        for (int i=head[u];i!=-;i=e[i].nxt){

            int v=e[i].to;

            int w=e[i].w;

            if (d[v]>d[u]+w){

                d[v]=d[u]+w;

                cnt[v]=cnt[u]+;

                if(cnt[v]>n) return true;

                if (!vis[v]){

                    vis[v]=true;

                    que.push(v);

                }

            }

        }

    }

    return false;

}

int main(){

    int a,b,c,T;

    scanf("%d",&T);

    while(T--){

        tot=;

        memset(head,-,sizeof head);

        memset(vis,,sizeof vis);

        memset(d,,sizeof d);

        scanf("%d%d",&n,&m);

        for(int i=;i<m;i++){//注意为双向边

            scanf("%d%d%d",&a,&b,&c);

            add_edge(a,b,c);

            if(c>=)add_edge(b,a,c);

        }

        if(spfa()) puts("YE5");

        else puts("N0");

    }

    return ;

}

3、bfs_spfa（num>n）

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<iostream>

#include<cmath>

#include<queue>

using namespace std;

const int inf=0x3f3f3f3f;

const int maxm=;

const int maxn=;

int head[maxn],tot,n,m,num[maxn],w;

struct edge{

    int to;

    int w;

    int nxt;

}e[maxm];

void add_edge(int u,int v,int w){

    e[tot].w=w;

    e[tot].to=v;

    e[tot].nxt=head[u];

    head[u]=tot++;

}

bool vis[maxn];

queue<int>que;//队列是点的队列

int d[maxn];

bool spfa(int s){

    memset(num,,sizeof num);

    fill(d+,d+n+,inf);

    memset(vis,,sizeof vis);

    while(!que.empty()) que.pop();

    que.push(s);

    vis[s]=true;

    d[s]=;

    while (!que.empty()){

        int u=que.front();

        que.pop();

        vis[u]=false;

        for (int i=head[u];i!=-;i=e[i].nxt){

            int v=e[i].to;

            int w=e[i].w;

            if (d[v]>d[u]+w){

                d[v]=d[u]+w;

                if (!vis[v]){

                    vis[v]=true;

                    que.push(v);//hash一下，可判断是否存在负环

                    num[v]++;

                    if(num[v]>n) return true;

                }

            }

        }

    }

    return false;

}

int main(){

    int a,b,c,T;

    scanf("%d",&T);

    while(T--){

        tot=;

        memset(head,-,sizeof head);

        memset(vis,,sizeof vis);

        memset(d,,sizeof d);

        scanf("%d%d",&n,&m);

        for(int i=;i<m;i++){//注意为双向边

            scanf("%d%d%d",&a,&b,&c);

            add_edge(a,b,c);

            if(c>=)add_edge(b,a,c);

        }

        if(spfa()) puts("YE5");

        else puts("N0");

    }

    return ;

}