题意分析

题目描述了一个名为 CSAD（道路补偿方案）的交通系统，其中车辆在道路上行驶时根据道路入口点支付税款或获得补偿。系统核心是寻找从起点 A 到终点 B 的“最优路径”，该路径需满足两个条件：

1. 奖励性（Rewarding）：路径中的每条道路必须是从当前节点出发的所有道路中入口费用最小的道路（可能有多条）。
2. 最小权重和长度：在所有满足最小权重（总费用和）的路径中，选择总长度最小的路径。

关键概念：

• 费用（Fee）：正数表示税款（支付），负数表示补偿（获得）。
• 权重（Weight）：路径中所有道路的费用总和。
• 长度（Length）：路径中所有道路的长度总和。
• 特殊输出：
  • VOID：无可行路径。
  • UNBOUND：存在负权环导致权重无限降低。

解题思路

1. 构建奖励性子图

• 最小费用边筛选：对每个节点 u，计算其所有出边的最小费用 min_fee[u]。保留所有费用等于 min_fee[u] 的边（可能有多个方向），删除费用更高的边。

2. 连通性检测（反向图DFS）

• 构建反向图：将原图的有向边反向，用于从终点 B 出发进行 DFS。
• 标记有效节点：从终点 B 开始 DFS，标记所有能到达 B 的节点。若起点 A 未被标记，输出 VOID。

3. 负权环检测与最短路计算（SPFA）

• SPFA算法优化：在奖励性子图上运行 SPFA，同时维护两个数组：
  • fee[i]：从起点到节点 i 的最小权重。
  • dis[i]：在最小权重前提下，从起点到节点 i 的最短长度。
• 负权环检测：若节点入队次数超过 n，判定存在负权环。若该环在 A→B 路径上，输出 UNBOUND。

4. 算法流程

graph TD
    A[输入：道路地图 n, m, A, B] --> B[构建原始图 G]
    B --> C[计算 min_fee[u]]
    C --> D[删除非奖励性边]
    D --> E[构建反向图 R]
    E --> F[从 B 开始 DFS 标记节点]
    F --> G{A 是否被标记？}
    G -- 否 --> H[输出 VOID]
    G -- 是 --> I[删除无效节点/边]
    I --> J[运行 SPFA]
    J --> K{检测到负权环？}
    K -- 是 --> L[输出 UNBOUND]
    K -- 否 --> M[输出 fee[B] 和 dis[B]]

示例代码

 #include <cstdio>
 #include <cstring>
 #include <algorithm>
 #include <queue>
 #include <vector>
 #define INF 0x3f3f3f3f
 using namespace std;
 #define N 1110
 struct edge
 {
     int l, w, v;
     edge () {}
     edge (int v, int w, int l) : v(v), w(w), l(l) {}
 };
 int st, ed, lfee[N], vis[N], dis[N], fee[N], cnt[N], n, m;
 vector <vector<edge> > G, R;
 //就是vector<edge> G[N];
 
 void add(vector<vector<edge> > &G, int u, int v, int w, int l)
 {
     G[u].push_back(edge(v, w, l));
 }
 
 //删除不是最小费用的边
 void edge_clear()
 {
     for(int i = 0; i < n; i++) {
         for(vector<edge>::iterator p = G[i].begin(); p != G[i].end(); ) {
             if(p->w > lfee[i]) {
                 p = G[i].erase(p);
             } else {
                 p++;
             }
         }
     }
 }
 
 //删除从起点到终点不会走过的点
 void node_clear()
 {
     for(int i = 0; i < n; i++) {
         if(!vis[i]) {
             G[i].clear();
             continue;
         }
         for(vector<edge>::iterator p = G[i].begin(); p != G[i].end(); ) {
             if(!vis[p->v]) {
                 p = G[i].erase(p);
             } else {
                 p++;
             }
         }
     }
 }
 
 //将图翻转
 void reg()
 {
     R = vector<vector<edge> > (n);
     for(int i = 0; i < n; i++) {
         for(vector<edge>::iterator p = G[i].begin(); p != G[i].end(); p++) {
             add(R, p->v, i, p->w, p->l);
         }
     }
 }
 
 //标记从终点走出去可以经过哪些点
 void dfs(int u)
 {
     vis[u] = 1;
     for(int i = 0; i < R[u].size(); i++) {
         int v = R[u][i].v;
         if(!vis[v]) dfs(v);
     }
 }
 
 bool spfa()
 {
     for(int i = 0; i <= n; i++) {
         dis[i] = INF; fee[i] = INF;
     }
     memset(vis, 0, sizeof(vis));
     memset(cnt, 0, sizeof(cnt));
     dis[st] = 0;
     fee[st] = 0;
     vis[st] = 1;
     queue <int> que;
     while(!que.empty()) que.pop();
     que.push(st);
     while(!que.empty()) {
         int u = que.front(); que.pop();
         cnt[u]++;
         if(cnt[u] > n) return false;
         vis[u] = 0;
         for(int i = 0; i < G[u].size(); i++) {
             int v = G[u][i].v, w = G[u][i].w, l = G[u][i].l;
             if(fee[v] >= fee[u] + w) {
                 if(fee[v] > fee[u] + w) {
                     fee[v] = fee[u] + w;
                     dis[v] = dis[u] + l;
                     if(!vis[v]) {
                         vis[v] = 1;
                         que.push(v);
                     }
                 } else if(dis[v] > dis[u] + l) {
                     dis[v] = dis[u] + l;
                     if(!vis[v]) {
                         vis[v] = 1;
                         que.push(v);
                     }
                 }
             }
         }
     }
 }
 
 int main()
 {
     while(~scanf("%d%d%d%d", &n, &m, &st, &ed)) {
         memset(lfee, INF, sizeof(lfee));
         G.clear(); R.clear();
         G = vector<vector<edge> > (n);
         for(int i = 0; i < m; i++) {
             int u, v, uv, vu, l;
             scanf(" (%d,%d,%d[%d]%d)", &u, &v, &uv, &l, &vu);
             add(G, u, v, uv, l);
             add(G, v, u, vu, l);
             if(lfee[u] > uv) lfee[u] = uv;
             if(lfee[v] > vu) lfee[v] = vu;
             //记录出边的最小的费用
         }
 
         memset(vis, 0, sizeof(vis));
         edge_clear();
         reg();
         dfs(ed);
         if(!vis[st]) {
             printf("VOID\n");
             continue;
         }
         node_clear();
         bool flag = spfa();
         if(!flag) printf("UNBOUND\n");
         else printf("%d %d\n", fee[ed], dis[ed]);
     }
     return 0;
 }

关键算法细节

• 时间复杂度：SPFA 平均 O(m)，最坏 O(n·m)（n≤1100, m≤5000 可接受）。
• 空间复杂度：O(n + m) 存储图结构和辅助数组。
• 处理特殊输入：使用 scanf(" (%d,%d,%d[%d]%d)") 解析带空格的输入。