【模板】负环

题目解析

代码 Bellman

cpp

#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
const int maxm=3005;
const int INF=1e9;

int t,n,m;
int d[maxn];
struct Edge{
    int v,w;
    Edge *next;
}pool[2*maxm],*h[maxn];
int cnt=0;
void Add_Edge(int u,int v,int w)
{
    Edge *p=&pool[cnt++];
    p->v=v;p->w=w;p->next=h[u],h[u]=p;
    if(w>=0)
    {
        Edge *q=&pool[cnt++];
        q->v=u;q->w=w;q->next=h[v],h[v]=q;  
    }
}

bool Bellman_Ford()
{
    fill(d,d+n+1,INF);
    d[1]=0;
    bool flag=false;
    for(int k=0;k<n;k++)
    {
        flag=false;
        for(int i=1;i<=n;i++)
        {
            if(d[i]<INF)
            {
                for(Edge *p=h[i];p;p=p->next)
                {
                    if(d[p->v]>d[i]+p->w)
                    {
                        d[p->v]=d[i]+p->w;
                        flag=true;
                    }
                }
            }
        }
        if(!flag) break;
    }
    return flag;
}
int main() 
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        cnt=0;
        for(int i=0;i<=n;i++) h[i]=NULL;//重置h[i] 
        int u,v,w;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            Add_Edge(u,v,w);
        }
        if(Bellman_Ford()) printf("YE5\n");
        else printf("N0\n");
    }
    return 0;
}

代码 spfa-dfs

在你去写这道题之前，我必须告诉你一个关于 DFS-SPFA 的残酷真相：

虽然 DFS-SPFA 在 01分数规划（如 P3199）中是神一般的存在（效率极高），但在 纯负环模板题（如 P3385）中，它很容易被“恶意数据”卡成 TLE (超时)。

原因：出题人可以构造一种特殊的网格图，让 DFS 一头扎进去遍历指数级的路径，导致这一条路“走到黑”要走很久才能撞到尾巴。
对策：如果你发现 TLE 了，不要怀疑你的算法逻辑（你的逻辑是对的）。为了过这道题，你可以尝试以下“玄学优化”：
1. 打乱顺序：在遍历节点 $1 \dots N$ 之前，用 random_shuffle 打乱顺序。
2. 累加限制：设置一个全局计数器，如果 DFS 调用次数超过一个巨大值（比如 $2 \times 10^7$ ），强行返回 true（这是一种赌博，赌它肯定有负环）。

**当然，如果你只想验证代码逻辑是否正确，即使 TLE 了也没关系，只要没有 WA (Wrong Answer) 就说明你的判环逻辑是对的。]

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;
const int INF = 1e9;

struct Edge {
    int to, w;
};
vector<Edge> adj[MAXN];
int dis[MAXN];
bool instack[MAXN];
bool visited[MAXN]; // 全局访问标记，用于剪枝
int n, m;

// DFS-SPFA
bool spfa_dfs(int u) {
    instack[u] = true;
    visited[u] = true; // 标记该点已访问，后续外层循环不用再进

    for (auto &e : adj[u]) {
        int v = e.to;
        int w = e.w;

        if (dis[v] > dis[u] + w) {
            dis[v] = dis[u] + w;
            if (instack[v]) return true; // 发现负环
            if (spfa_dfs(v)) return true;
        }
    }
    instack[u] = false;
    return false;
}

void solve() {
    cin >> n >> m;
    
    // 1. 清空数据 (多测不清空，爆零两行泪)
    for (int i = 1; i <= n; i++) {
        adj[i].clear();
        dis[i] = 0; // 判负环初始化为 0
        instack[i] = false;
        visited[i] = false;
    }

    // 2. 读入
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (w >= 0) {
            // 题目说：非负边是双向的
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        } else {
            // 负边是单向的
            adj[u].push_back({v, w});
        }
    }

    // 3. 判负环
    bool flag = false;
    for (int i = 1; i <= n; i++) {
        if (visited[i]) continue; // 剪枝：如果这个连通块搜过了，就跳过
        if (spfa_dfs(i)) {
            flag = true;
            break;
        }
    }

    if (flag) cout << "YES" << endl;
    else cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

目录

题目解析

代码 Bellman

代码 spfa-dfs