题目分析

本题要求我们在一个有向图中选择若干条边进行粉刷，使得：

1. 被粉刷的边可以划分成若干个不相交的环
2. 每个顶点恰好出现在 $k$ 个环中
3. 最小化粉刷边的总成本

关键条件转化

题目中两个核心约束需要仔细分析：

约束一：每个顶点出现在 $k$ 个环中

• 在一个环中，每个顶点恰好有一条出边和一条入边
• 因此，如果一个顶点出现在 k 个环中，意味着它有 $k$ 条出边 和 $k$ 条入边 被选中
• 于是，每个顶点的出度 = 入度 = $$k

约束二：被粉刷的边可以划分成若干个不相交的环

• 对于一个有向图，如果每个顶点的出度 = 入度，那么该图的边集一定可以分解成若干个有向环（欧拉定理）
• 因此，这个约束等价于：被粉刷的边构成的子图中，每个顶点的出度 = 入度

综合两个约束：我们需要选择一个边的子集，使得每个顶点的出度 = 入度 = $k$，并最小化被选边的总费用。

模型抽象

这是一个典型的流量平衡问题：

• 每个顶点需要流出 $k$ 个单位（出度要求）
• 每个顶点需要流入 $k$ 个单位（入度要求）
• 每条边 ($u$ → $v$) 可以选择或不选，如果选择则 $u$ 流出 $1$，$v$ 流入 $1$，并产生费用

这正是最小费用流可以解决的模型。

---

解题思路

拆点建图

将每个顶点 $i$ 拆成两个节点：

• 左点 $L_i$：代表顶点的出边端
• 右点 $R_i$：代表顶点的入边端

建图方式：

1. 建立超级源点 $S$，向每个左点 $L_i$ 连边，容量为 $k$，费用为 $0$
   → 表示顶点 $i$ 需要有 $k$ 个出度

2. 建立超级汇点 $T$，每个右点 $R_i$ 向 $T$ 连边，容量为 $k$，费用为 $0$
   → 表示顶点 $i$ 需要有 $k$ 个入度

3. 对于原图中的每条有向边 $(u\to v)$，长度为 $d$：
   从左点 $L_u$ 到右点 $R_v$ 连边，容量为 $1$，费用为 $d$
   → 表示选择这条边时，$u$ 贡献 $1$ 个出度，$v$ 贡献 $1$ 个入度，花费 $d$

流量含义

• 从 $S$ 到 $L_u$ 的流量：顶点 $u$ 被选中的出边数量
• 从 $L_u$ 到 $R_v$ 的流量：边 $(u,v)$ 被选中
• 从 $R_v$ 到 $T$ 的流量：顶点 $v$ 被选中的入边数量

总流量 = ${\sum }_i{\text{出度}}_i=k\times n$
总费用 = 所有被选边的长度之和

可行性判断

• 跑 最小费用最大流，得到最大流量 $flow$ 和最小费用 $cost$
• 如果 $flow=k\times n$，说明每个顶点的出度入度都达到了 $k$，可行，答案为 $cost$
• 否则，无法满足条件，输出 $-1$

复杂度分析

• 节点数：$2n+2\le 82$
• 边数：$m+2n\le 2080$
• 流量值：$k\times n\le 100$
• 使用 $\text{SPFA}$ 实现的费用流，复杂度 $O(F\cdot E\cdot V)$，完全可行

---

正确性证明

必要性：如果存在满足条件的边集，则每个顶点出度 = 入度 = $k$。在流网络中，令 $S\to L_i$ 通过 $k$ 单位流量，对于每条被选的边 $(u,v)$，在 $L_u\to R_v$ 上通过 $1$ 单位流量，$R_v\to T$ 也能收到对应流量。这样得到一个流量为 $k\times n$ 的可行流，费用等于边权和。因此最小费用流不会大于最优解。

充分性：如果最小费用流得到 $flow=k\times n$，则每个 $S\to L_i$ 和 $R_i\to T$ 都流满 $k$，即每个顶点的出度 = 入度 = $k$。由欧拉定理，这样的有向图可以分解成若干个环，满足题意。且费用流保证了总费用最小。

---

注意事项

1. 重边处理：题目保证两个城市之间同方向最多一条路，因此每条边建一次容量为 $1$ 即可
2. 零费用边：边长度可能为 $0$，不影响算法
3. 多测试用例：每次重新初始化费用流结构体
4. 变量命名冲突：代码中汇点变量名不要和测试用例数 $T$ 冲突，故将测试用例数命名为 $\text{TT}$

---

代码实现

// Paint the Roads
// UVa ID: 12092
// Verdict: Accepted
// Submission Date: 2026-02-12
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;

struct MCMF {
    struct Edge {
        int to, cap, cost, rev;
    };
    int n;
    vector<vector<Edge>> g;
    vector<int> dist, preNode, preEdge;
    vector<bool> inq;
    
    MCMF(int n) : n(n) {
        g.resize(n);
        dist.resize(n);
        preNode.resize(n);
        preEdge.resize(n);
        inq.resize(n);
    }
    
    void addEdge(int from, int to, int cap, int cost) {
        g[from].push_back({to, cap, cost, (int)g[to].size()});
        g[to].push_back({from, 0, -cost, (int)g[from].size() - 1});
    }
    
    bool spfa(int s, int t, int &flow, int &cost) {
        fill(dist.begin(), dist.end(), INF);
        fill(inq.begin(), inq.end(), false);
        dist[s] = 0;
        queue<int> q;
        q.push(s);
        inq[s] = true;
        preNode[s] = -1;
        
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for (int i = 0; i < (int)g[u].size(); i++) {
                Edge &e = g[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    preNode[e.to] = u;
                    preEdge[e.to] = i;
                    if (!inq[e.to]) {
                        q.push(e.to);
                        inq[e.to] = true;
                    }
                }
            }
        }
        if (dist[t] == INF) return false;
        
        int f = INF;
        for (int v = t; v != s; v = preNode[v]) {
            int u = preNode[v];
            f = min(f, g[u][preEdge[v]].cap);
        }
        flow += f;
        cost += f * dist[t];
        for (int v = t; v != s; v = preNode[v]) {
            int u = preNode[v];
            Edge &e = g[u][preEdge[v]];
            e.cap -= f;
            g[e.to][e.rev].cap += f;
        }
        return true;
    }
    
    PII minCostMaxFlow(int s, int t) {
        int flow = 0, cost = 0;
        while (spfa(s, t, flow, cost));
        return {flow, cost};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int TT;
    cin >> TT;
    while (TT--) {
        int n, m, k;
        cin >> n >> m >> k;
        
        // 节点编号：
        // 0 ~ n-1: 左点 (出点)
        // n ~ 2n-1: 右点 (入点)
        // 2n: 源点 S
        // 2n+1: 汇点 T
        int S = 2 * n, T = 2 * n + 1;
        MCMF mcmf(2 * n + 2);
        
        // 源点到左点，容量 k，费用 0
        for (int i = 0; i < n; i++)
            mcmf.addEdge(S, i, k, 0);
        
        // 右点到汇点，容量 k，费用 0
        for (int i = 0; i < n; i++)
            mcmf.addEdge(i + n, T, k, 0);
        
        // 读入道路
        for (int i = 0; i < m; i++) {
            int f, t, d;
            cin >> f >> t >> d;
            // 左点 f 到右点 t+n，容量 1，费用 d
            mcmf.addEdge(f, t + n, 1, d);
        }
        
        PII r = mcmf.minCostMaxFlow(S, T);
        if (r.first == k * n) cout << r.second << '\n';
        else cout << -1 << '\n';
    }
    return 0;
}