虫洞

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1857 字
虫洞建负边Bellman-Ford判负环
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1507
// 题意：F 个农场，每个有 N 块地、M 条双向小路（耗时 T）与 W 个虫洞（有向，回到 T 秒前），问能否回到出发点之前的时刻。
// 思路：虫洞建成负权有向边，小路建成两条正权有向边，从虚拟源点做 Bellman-Ford 判全图负环，有负环即 YES。
// 1. dis 全部初始化为 0 等价于虚拟源点连向所有点，能一次判出图中任意位置的负环。
// 2. 数据范围很小，Bellman-Ford 直接跑 N 轮即可，不必上 SPFA。
// 复杂度：O(F * n * (m + w)) 时间 / O(n) 空间
// 易错点：小路是双向的、虫洞是单向的，别把虫洞也建成双向边。
// 易错点：判定要在第 N 轮仍能松弛才算负环，提前退出要用「本轮无更新」而不是固定跑一轮。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 505;
struct Edge{
    int to;
    int w;
};
vector<Edge> g[MAXN];
int main(){
    int F;
    if(!(cin >> F)) return 0;
    while(F--){
        int n, m, wnum;
        cin >> n >> m >> wnum;
        for(int i = 1; i <= n; i++){
            g[i].clear();
        }
        for(int i = 0; i < m; i++){
            int a, b, t;
            cin >> a >> b >> t;
            Edge x;
            x.to = b;
            x.w = t;
            g[a].push_back(x);
            Edge y;
            y.to = a;
            y.w = t;
            g[b].push_back(y);
        }
        for(int i = 0; i < wnum; i++){
            int a, b, t;
            cin >> a >> b >> t;
            Edge x;
            x.to = b;
            x.w = -t;
            g[a].push_back(x);
        }
        vector<int> dis(n + 1, 0);
        bool neg = false;
        for(int i = 1; i <= n; i++){
            bool upd = false;
            for(int u = 1; u <= n; u++){
                for(int k = 0; k < (int)g[u].size(); k++){
                    int v = g[u][k].to;
                    int w = g[u][k].w;
                    if(dis[v] > dis[u] + w){
                        dis[v] = dis[u] + w;
                        upd = true;
                    }
                }
            }
            if(!upd) break;
            if(i == n) neg = true;
        }
        if(neg) cout << "YES" << "\n";
        else cout << "NO" << "\n";
    }
    return 0;
}
虫洞

正文

一本通·提高篇的其它内容
