农场时间旅行问题题解

一、题目分析

题目要求判断农场中是否存在时间回路，即从某块田地出发，经过若干路径和虫洞后回到起点时的时间早于出发时间。关键条件：

1. 路径是双向的，虫洞是单向的且会回溯时间；
2. 需判断是否存在负权回路（时间减少的回路）。

二、算法思路

1. 负权回路检测：

   • 虫洞的时间回溯相当于负权边（时间减少）；
   • 使用Bellman-Ford算法检测图中是否存在负权回路。

2. Bellman-Ford算法：

   • 初始化距离数组，源点距离为0，其他为无穷大；
   • 进行n-1次松弛操作（n为节点数）；
   • 若第n次松弛仍能更新距离，说明存在负权回路。

三、代码实现

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 550;
int dist[MAXN];  // 距离数组

struct Edge {
    int u, v;  // 边的起点和终点
    int cost;  // 边的权值（时间）
    Edge(int _u = 0, int _v = 0, int _cost = 0) : u(_u), v(_v), cost(_cost) {}
};

vector<Edge> E;  // 存储所有边

// Bellman-Ford算法检测负权回路
bool bellman_ford(int start, int n) {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[start] = 0;  // 源点距离初始化为0
    
    for (int i = 1; i < n; i++) {  // 最多松弛n-1次
        bool flag = false;
        for (int j = 0; j < E.size(); j++) {
            int u = E[j].u;
            int v = E[j].v;
            int cost = E[j].cost;
            if (dist[v] > dist[u] + cost) {  // 松弛操作
                dist[v] = dist[u] + cost;
                flag = true;
            }
        }
        if (!flag) return true;  // 没有松弛，提前终止
    }
    
    // 检查是否存在负权回路
    for (int j = 0; j < E.size(); j++)
        if (dist[E[j].v] > dist[E[j].u] + E[j].cost)
            return false;  // 存在负权回路
    return true;  // 不存在负权回路
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        E.clear();  // 清空边集合
        int n, m, w;
        cin >> n >> m >> w;
        
        // 读取双向路径
        for (int j = 0; j < m; j++) {
            int u, v, cost;
            cin >> u >> v >> cost;
            E.push_back(Edge(u, v, cost));
            E.push_back(Edge(v, u, cost));  // 双向边
        }
        
        // 读取虫洞（单向负权边）
        for (int j = 0; j < w; j++) {
            int u, v, cost;
            cin >> u >> v >> cost;
            E.push_back(Edge(u, v, -cost));  // 虫洞回溯时间，转化为负权边
        }
        
        // 检测是否存在负权回路
        if (!bellman_ford(1, n)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

四、代码解释

1. 输入处理：

   • 读取农场数量t，逐个处理每个农场；
   • 路径是双向的，添加两条方向相反的边；
   • 虫洞是单向的，添加一条负权边（时间回溯转化为负权）。

2. Bellman-Ford算法：

   • 初始化距离数组，源点（田地1）距离为0；
   • 进行n-1次松弛，若某轮无更新则提前终止；
   • 最后检查是否存在可松弛的边，存在则有负权回路。

3. 结果判断：

   • 若存在负权回路，输出"YES"，否则输出"NO"。

五、示例解析

输入样例2：

3 2 1  
1 2 3  
2 3 4  
3 1 8  

1. 边构建：

   • 路径1-2（3）、2-1（3）；
   • 路径2-3（4）、3-2（4）；
   • 虫洞3-1（-8）。

2. 松弛过程：

   • 初始dist[1]=0，其他为INF；
   • 第1次松弛：dist[2]=3，dist[3]=7（1→2→3）；
   • 第2次松弛：dist[1]=7+(-8)=-1（3→1）；
   • 第3次检查：dist[1]可通过3→1进一步松弛，存在负权回路。

3. 输出：

   YES  
   

六、复杂度分析

• 时间复杂度：O(F×(N×M))，其中F为农场数，N为节点数，M为边数；
• 空间复杂度：O(M)，存储边集合。

七、关键技巧

1. 负权边转换：虫洞的时间回溯转化为负权边；
2. Bellman-Ford应用：利用算法检测负权回路，适用于存在负权边的图；
3. 提前终止优化：若某轮松弛无更新，提前终止循环。