图论综合应用：最短路径优化与正环判定
聚会往返最短时间分析
在农场网络规划场景中，常需计算节点间的往返最优耗时。假设有 N 个农场编号为 1 到 N，其中 X 号农场举办聚会。已知 M 条单向道路及其通行时长，目标是找出所有牛只从各自所在地出发前往 X 并返回原处的过程中，消耗时间的最大值。
该问题本质上是求解单源最短路的双向组合。对于任意节点 i，其总耗时等于"i 到 X 的最短距离"加上"X 到 i 的最短距离"。由于图是有向的，直接求所有点到 X 的距离效率较低。
解决方案采用两次迪杰斯特拉（Dijkstra）算法：
- 正向图搜索：以 X 为起点，计算 X 到达其余各点的最短路径，即返程耗时。
- 反向图搜索：构建原图的逆拓扑结构（将所有有向边反转），再次以 X 为起点运行算法。此时算出的 X 到其他点的距离，等价于原图中其他点到 X 的距离，即去程耗时。
遍历所有节点，累加两次的结果并取最大值即可。
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
struct Edge {
int target;
int weight;
};
int totalNodes, totalEdges, hostId;
vector<Edge> graph[MAXN]; // 正向邻接表
vector<Edge> revGraph[MAXN]; // 反向邻接表
int distTo[MAXN], distFrom[MAXN];
// 优先队列优化的 Dijkstra 算法
void computePaths(int startNode, const vector<Edge> graph[], int result[]) {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
fill(result, result + totalNodes + 1, INF);
result[startNode] = 0;
pq.push({0, startNode});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (d > result[u]) continue;
for (const auto& edge : graph[u]) {
if (result[edge.target] > d + edge.weight) {
result[edge.target] = d + edge.weight;
pq.push({result[edge.target], edge.target});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (!(cin >> totalNodes >> totalEdges >> hostId)) return 0;
for (int i = 0; i < totalEdges; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
revGraph[v].push_back({u, w}); // 构建反向图
}
// 计算从 X 出发的最短距离（返程时间）
computePaths(hostId, graph, distFrom);
// 计算从 X 出发在反向图中的距离（等同于去往 X 的时间）
computePaths(hostId, revGraph, distTo);
int maxTotalTime = 0;
for (int i = 1; i <= totalNodes; ++i) {
if (distFrom[i] != INF && distTo[i] != INF) {
maxTotalTime = max(maxTotalTime, distFrom[i] + distTo[i]);
}
}
cout << maxTotalTime << endl;
return 0;
}货币交易套利判定
另一种常见的图论模型涉及资金流转与汇率变动。给定若干种货币及它们之间的兑换规则（包含汇率和手续费），需要判断是否存在一种兑换序列，使得最终持有金额高于初始金额。若存在此类环路，则意味着可以通过无限循环兑换获取无限财富。
这属于最长路问题中的正环检测变种。传统的负权回路检测通常用于寻找最小值陷入死循环的情况，而此处是寻找最大值增长的正反馈回路。我们可以使用 SPFA（队列优化的 Bellman-Ford）算法进行判定。
核心逻辑在于松弛操作：如果通过某种货币兑换能增加当前持有的钱数，则更新距离数组。统计每个节点的入队次数，若某节点被更新次数超过节点总数 N，说明图中存在可以让价值不断增大的正环。
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;
const int MAX_NODES = 110;
struct Transaction {
int to;
double rate;
double commission;
};
int n, m, startCurrency;
double initialCapital;
vector<Transaction> adj[MAX_NODES];
double currentVal[MAX_NODES];
int updateCount[MAX_NODES];
bool inQueue[MAX_NODES];
bool detectProfitLoop() {
queue<int> q;
memset(inQueue, false, sizeof(inQueue));
memset(updateCount, 0, sizeof(updateCount));
memset(currentVal, 0, sizeof(double) * (n + 1));
currentVal[startCurrency] = initialCapital;
q.push(startCurrency);
inQueue[startCurrency] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
inQueue[u] = false;
for (const auto& trans : adj[u]) {
int v = trans.to;
// 计算兑换后的新金额：(当前金额 - 手续费) * 汇率
double newVal = (currentVal[u] - trans.commission) * trans.rate;
if (newVal > currentVal[v] + 1e-8) {
currentVal[v] = newVal;
updateCount[v]++;
// 若更新次数达到节点数，存在正环
if (updateCount[v] >= n) return true;
if (!inQueue[v]) {
q.push(v);
inQueue[v] = true;
}
}
}
}
return false;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
while (cin >> n >> m >> startCurrency >> initialCapital) {
for (int i = 0; i <= n; ++i) adj[i].clear();
for (int i = 0; i < m; ++i) {
int u, v;
double r_uv, c_uv, r_vu, c_vu;
cin >> u >> v >> r_uv >> c_uv >> r_vu >> c_vu;
adj[u].push_back({v, r_uv, c_uv});
adj[v].push_back({u, r_vu, c_vu});
}
if (detectProfitLoop()) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
return 0;
}