题目大意

$\text{Megacity}$ 市由若干个单向道路连接基站点构成。每个道路可以选择巡逻（成本 $p$）或视频监控（成本 $s$）。要求：

1. 流量平衡：每个基站的出度等于入度（形成欧拉回路）
2. 必须巡逻：某些道路必须被巡逻（$x=1$）
3. 至少一条巡逻：整个系统中至少有一条道路被巡逻

目标是在满足上述约束下，最小化总监控成本。

算法思路分析

1. 问题建模

这是一个带约束的最小费用流问题。我们将问题转化为网络流模型：

• 节点：$n$ 个基站 + 源点 $src=n+1$ + 汇点 $sink=n+2$
• 流量：表示巡逻的道路数量
• 费用：选择巡逻而非视频监控的额外成本

2. 流量平衡约束

对于每个基站 $i$，要求：
$$\text{出度}(i)=\text{入度}(i)$$

在网络流中，我们通过源点和汇点来保证这一平衡：

• 源点向需要额外流入的节点提供流量
• 需要额外流出的节点向汇点输送流量

3. 道路处理策略

情况 1：必须巡逻的道路（$x=1$）

if (x == 1) {
    baseCost += p;           // 直接计入巡逻成本
    requiredFlow++;          // 增加所需流量
    addEdge(src, v, 1, 0);   // 源点向v提供1单位流入
    addEdge(u, sink, 1, 0);  // u向汇点提供1单位流出
}

• 成本：直接计入巡逻成本 $p$
• 流量：必须满足 1 单位流量
• 约束：添加流量平衡边

情况 2：巡逻成本更高（$p\ge s$）

if (p >= s) {
    baseCost += s;           // 基础成本为视频监控成本
    addEdge(u, v, 1, p - s); // 选择巡逻的额外成本为(p-s)
}

• 基础选择：视频监控（成本 $s$）
• 可选巡逻：额外成本 $p-s$

情况 3：巡逻成本更低（$p<s$）

else {
    baseCost += p;           // 基础成本为巡逻成本
    requiredFlow++;          // 增加所需流量
    addEdge(v, u, 1, s - p); // 反向边表示节省(s-p)
    addEdge(src, v, 1, 0);   // 流量平衡约束
    addEdge(u, sink, 1, 0);
}

• 基础选择：巡逻（成本 $p$）
• 可选视频监控：可节省 $s-p$（通过反向边实现）

4. 关键优化：最小环检测

当计算得到的总成本等于全视频监控成本时：
$$totalCost=videoCost$$

说明没有道路被巡逻，违反了"至少一条巡逻道路"的约束。此时需要找到最小成本的巡逻环。

// 使用Floyd算法找最小环
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (cycle[i][k] < INF && cycle[k][j] < INF && 
                cycle[i][j] > cycle[i][k] + cycle[k][j]) {
                cycle[i][j] = cycle[i][k] + cycle[k][j];
            }
        }
    }
}

最小环原理：

• $cycle[i][j]=p-s$ 表示从 $i$ 到 $j$ 选择巡逻的额外成本
• 最小自环 $cycle[i][i]$ 表示经过 $i$ 的最小巡逻环
• 最终成本：$minCycle+videoCost$

5. 算法正确性证明

1. 流量平衡保证：通过源汇点的流入流出约束，确保每个节点满足：
   $$\sum \text{流入}=\sum \text{流出}$$

2. 成本最小化：最小费用流算法保证在满足流量约束下成本最小

3. 巡逻约束处理：

   • 必须巡逻：通过固定流量处理
   • 至少一条巡逻：通过最小环检测保证

4. 最优性：网络流模型覆盖所有可能的巡逻方案，Floyd 算法找到全局最小环

复杂度分析

• 网络流：$O(V\cdot E\cdot f)$，其中 $V\le 102$，$E\le 1000$，$f\le 1000$
• $\text{Floyd-Warshall}$ 算法：$O(n^3)$，$n\le 100$
• 总体复杂度：在题目约束下完全可行

参考代码

// Highway Patrol
// UVa ID: 1259
// Verdict: Accepted
// Submission Date: 2025-10-09
// UVa Run Time: 0.090s
//
// 版权所有（C）2025，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>

using namespace std;

const int INF = 1000000000;
const int MAXN = 500;
const int MAXM = 5000;

// 边结构体：用于表示网络流中的边
struct Edge {
    int v, f, w, nxt;  // v: 终点, f: 剩余流量, w: 单位费用, nxt: 下一条边索引
    Edge() {}
    Edge(int v, int f, int w, int nxt) : v(v), f(f), w(w), nxt(nxt) {}
};

Edge edges[MAXM];        // 边数组
int head[MAXN], edgeCount; // 邻接表头指针，边计数器
int dist[MAXN], pre[MAXN], preEdge[MAXN]; // SPFA相关数组
bool inQueue[MAXN];      // SPFA队列标记
int src, sink;           // 源点和汇点
int maxflow;             // 最大流量

// 初始化网络流
void initialize() {
    edgeCount = 1;        // 从1开始，方便异或操作获取反向边
    memset(head, 0, sizeof(head));
    maxflow = 0;
}

// 添加边：u->v，容量f，费用w
void addEdge(int u, int v, int f, int w) {
    edges[++edgeCount] = Edge(v, f, w, head[u]);
    head[u] = edgeCount;
    // 添加反向边，容量0，费用-w，用于回流
    edges[++edgeCount] = Edge(u, 0, -w, head[v]);
    head[v] = edgeCount;
}

// SPFA算法寻找增广路
bool spfa() {
    queue<int> q;
    for (int i = 0; i <= sink; i++) {
        dist[i] = INF;      // 初始距离为无穷大
        inQueue[i] = false;
    }
    dist[src] = 0;          // 源点距离为0
    inQueue[src] = true;
    q.push(src);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inQueue[u] = false;
        
        // 遍历u的所有出边
        for (int i = head[u]; i; i = edges[i].nxt) {
            int v = edges[i].v;
            // 如果边有剩余容量且可以松弛
            if (edges[i].f > 0 && dist[u] + edges[i].w < dist[v]) {
                dist[v] = dist[u] + edges[i].w;
                pre[v] = u;             // 记录前驱节点
                preEdge[v] = i;         // 记录前驱边
                
                if (!inQueue[v]) {
                    inQueue[v] = true;
                    q.push(v);
                }
            }
        }
    }
    return dist[sink] < INF;  // 判断是否找到增广路
}

// 沿增广路增流
int augment() {
    int u = sink, delta = INF;
    
    // 寻找增广路上的最小剩余容量
    while (u != src) {
        if (edges[preEdge[u]].f < delta) 
            delta = edges[preEdge[u]].f;
        u = pre[u];
    }
    
    // 沿增广路更新流量
    u = sink;
    while (u != src) {
        edges[preEdge[u]].f -= delta;      // 正向边减流
        edges[preEdge[u] ^ 1].f += delta;  // 反向边加流
        u = pre[u];
    }
    
    maxflow += delta;  // 更新总流量
    return dist[sink] * delta;  // 返回本次增流的费用
}

// 最小费用最大流主函数
int minCostFlow() {
    int totalCost = 0;
    while (spfa()) totalCost += augment();  // 不断寻找增广路直到找不到为止
    return totalCost;
}

int main(int argc, char* argv[]) {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    
    int T; cin >> T;
    for (int caseNum = 1; caseNum <= T; caseNum++) {
        int n, m; cin >> n >> m;
        
        // 网络流建模：源点为n+1，汇点为n+2
        src = n + 1, sink = n + 2;
        initialize();
        
        int videoCost = 0;      // 所有边都使用视频监控的总成本
        int baseCost = 0;       // 基础成本（根据选择策略）
        int requiredFlow = 0;   // 需要满足的流量（必须巡逻的边数）
        
        // cycle数组用于存储最小环信息：cycle[u][v] = 巡逻成本 - 视频监控成本
        vector<vector<int>> cycle(n + 1, vector<int>(n + 1, INF));
        
        // 处理每条道路
        for (int i = 0; i < m; i++) {
            int u, v, p, s, x; 
            cin >> u >> v >> p >> s >> x;
            
            // 记录巡逻相对于视频监控的成本差异
            cycle[u][v] = p - s;
            // 累加视频监控总成本（假设所有边都用视频监控）
            videoCost += s;
            
            if (x == 1) {
                // 情况1：必须巡逻的道路
                baseCost += p;           // 直接计入巡逻成本
                requiredFlow++;          // 增加所需流量
                // 流量平衡约束：v节点需要流入，u节点需要流出
                addEdge(src, v, 1, 0);   // 源点向v提供1单位流入
                addEdge(u, sink, 1, 0);  // u向汇点提供1单位流出
            } else {
                if (p >= s) {
                    // 情况2：巡逻成本更高，优先视频监控，但可选择巡逻
                    baseCost += s;       // 基础成本为视频监控成本
                    // 添加可选边：选择巡逻的额外成本为(p-s)
                    addEdge(u, v, 1, p - s);
                } else {
                    // 情况3：巡逻成本更低，强制巡逻
                    baseCost += p;       // 基础成本为巡逻成本
                    requiredFlow++;      // 增加所需流量
                    // 反向边：表示如果选择视频监控可以节省(s-p)
                    addEdge(v, u, 1, s - p);
                    // 流量平衡约束
                    addEdge(src, v, 1, 0);
                    addEdge(u, sink, 1, 0);
                }
            }
        }
        
        // 计算最小费用流
        int flowCost = minCostFlow();
        
        printf("Case %d: ", caseNum);
        
        // 检查流量约束是否满足
        if (maxflow != requiredFlow) {
            printf("impossible\n");
            continue;
        }
        
        int totalCost = baseCost + flowCost;
        
        // 关键优化：如果总成本等于全视频监控成本，说明没有边被巡逻
        // 但题目要求至少有一条边被巡逻，需要找最小巡逻环
        if (totalCost == videoCost) {
            // 使用Floyd算法找最小环
            for (int k = 1; k <= n; k++) {
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        // 松弛操作，注意防止整数溢出
                        if (cycle[i][k] < INF && cycle[k][j] < INF && 
                            cycle[i][j] > cycle[i][k] + cycle[k][j]) {
                            cycle[i][j] = cycle[i][k] + cycle[k][j];
                        }
                    }
                }
            }
            
            // 在所有自环中找最小值（自环表示巡逻环）
            baseCost = INF;
            for (int i = 1; i <= n; i++) 
                baseCost = min(baseCost, cycle[i][i]);
            
            if (baseCost == INF) 
                printf("impossible\n");  // 找不到巡逻环
            else 
                // 最小环成本 + 视频监控基础成本
                printf("%d\n", baseCost + videoCost);
        } else {
            // 正常情况：直接输出计算得到的最小成本
            printf("%d\n", totalCost);
        }
    }
    return 0;
}

总结

本题通过巧妙的网络流建模，将复杂的图论约束转化为标准的最小费用流问题。算法核心在于：

1. 流量平衡建模：通过源汇点处理欧拉回路约束
2. 费用优化：合理设置边费用实现成本最小化
3. 约束保证：通过固定流量和最小环检测满足巡逻约束

该解法在 $O(n^3)$ 时间内解决问题，完全满足题目规模要求，体现了组合优化问题的经典求解思路。