追查坏牛奶

形式化题目

有 $n$ 个仓库（节点）和 $m$ 条单向运输线路（有向边，各带停运损失 $c$ ）。仓库 $1$ 是坏牛奶的发货工厂，仓库 $n$ 是零售商。要停运若干条线路，使坏牛奶无法从 $1$ 送达 $n$ ，要求：

停运损失总和最小（主目标）；
总和相同时，停运的线路数最少（次级目标）。

输出最小总损失、最少线路数，以及这些线路的输入行号（从小到大）。

从数学结构看，这是带权有向图上的 s-t 最小割：把节点分成含 $1$ 的集合 $A$ 与含 $n$ 的集合 $B$ ，停运所有从 $A$ 指向 $B$ 的边。

样例输入与输出（milk60 数据）：

text

text

1
260 1
3

下面用样例网络演示“割”的含义，★ 标出的边就是最终要停运的线路：

flowchart LR
    n1((1 工厂)) -->|"线路1 100"| n3((3))
    n3 -->|"线路2 50"| n2((2))
    n2 -->|"★线路3 60"| n4((4 零售商))
    n1 -->|"线路4 40"| n2
    n2 -->|"线路5 80"| n3

把节点分成 $A=\{1,2,3\}$ 、 $B=\{4\}$ 时，只有线路 3（ $2\to4$ ）从 $A$ 指向 $B$ ，割值恰好是它的代价 60。下表对比了几个候选割，可见 60 就是最小割值，且只含一条边：

$A$ 侧节点	跨过 $A\to B$ 的线路	总代价
$\{1,2,3\}$	线路3（60）	60 ← 最优
$\{1\}$	线路1（100）、线路4（40）	140
$\{1,3\}$	线路2（50）、线路4（40）	90
$\{1,2\}$	线路1（100）、线路5（80）	180

正解

思路

1. 先认出来：这就是最小割。 最朴素的思路是枚举停运哪些线路再检查连通性，有 $2^m$ 种；换一种枚举（把节点划成两组，统计组间线路）也有 $2^{n-2}$ 种，两者都不可行。但第二个枚举暴露了本质：任何“删掉边后 $1$ 到不了 $n$ ”的方案，都完整覆盖了某个顶点二分 $(A,B)$ （ $1\in A$ 、 $n\in B$ ）的全部跨边。所以问题退化成：找总代价最小的顶点二分—— 这正是最小割，而“最小割值 = 最大流值”可以一次 Dinic 求出。

2. 次级目标“线路数最少”用容量变换吸收。 普通最大流只保证主目标。把每条边的容量改成

w_e = c_e \cdot K + 1, \qquad K = m + 1

那么任意割的新容量 $= K \cdot (\text{原代价}) + (\text{边数})$ 。因为任何割的边数都不超过 $m < K$ ，比较两个割的新容量时，“商”先分胜负（原代价小者赢），“余数”再分胜负（边数少者赢）。于是修改图上的最小割，就是原图“总代价最小、其次边数最少”的割，两个目标一步到位。

3. 找出具体是哪几条线路：贪心逐条删测流。 最大流算法只给“割值”，还要把割边找出来。在当前图上临时删掉边 $e$ 再重跑一次最大流，观察最大流的变化：

若恰好减少了 $w_e$ （等于 $e$ 自己的修改容量），说明任何最大流都无法绕开 $e$ ， $e$ 必然属于当前图的某个最小割 —— 保留删除，计入答案；
若减少不足 $w_e$ ，说明流量可以绕行， $e$ 不在最小割里 —— 恢复容量。

按输入顺序处理完全部 $m$ 条边后，被保留删除的线路恰好组成了那个最优割：每条计入答案的边贡献 $c_e\cdot K + 1$ ，总削减量正好等于修改图的最大流 $F$ ，所以最小损失是 $F \div K$ 、最少线路数是 $F \bmod K$ ，答案行号天然按输入顺序排列。若 $1$ 本来就到不了 $n$ ， $F=0$ ，输出 0 0。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 07:30
# update_at: 2026-10-01 07:30

import sys
from collections import deque

INF = 10**18  # 增广时的“无穷大”上界


def dinic(adj: list[list[int]], to: list[int], caps: list[int], n: int) -> int:
    """当前容量 caps 下，节点 1 到节点 n 的最大流（Dinic 算法）。"""
    flow = 0
    s, t = 1, n
    while True:
        level = [-1] * (n + 1)  # BFS 分层
        level[s] = 0
        dq = deque([s])
        while dq:
            u = dq.popleft()
            for eid in adj[u]:
                v = to[eid]
                if caps[eid] > 0 and level[v] < 0:
                    level[v] = level[u] + 1
                    dq.append(v)
        if level[t] < 0:  # 汇点不可达，当前流已是最大流
            return flow

        it = [0] * (n + 1)  # 每个节点的弧指针：只扫一遍被拒绝的弧

        def push(u: int, f: int) -> int:
            """沿 level 严格递增的路径把流量 f 尽量送到汇点，返回实际送出量。"""
            if u == t:
                return f
            while it[u] < len(adj[u]):
                eid = adj[u][it[u]]
                v = to[eid]
                if caps[eid] > 0 and level[v] == level[u] + 1:
                    d = push(v, min(f, caps[eid]))
                    if d:
                        caps[eid] -= d
                        caps[eid ^ 1] += d
                        return d
                it[u] += 1
            return 0

        while True:
            d = push(s, INF)
            if not d:
                break
            flow += d


def make_caps(removed: list[bool], W: list[int], m: int) -> list[int]:
    """按 removed 状态重建容量数组：已移除的边容量为 0，其余为修改容量。"""
    caps = [0] * (2 * m)
    for i in range(m):
        if not removed[i]:
            caps[2 * i] = W[i]
    return caps


def extract_cut_edges(adj: list[list[int]], to: list[int], n: int, m: int, W: list[int]) -> tuple[int, list[int]]:
    """贪心提取最小割：返回 (修改图最大流, 按输入顺序排列的割边行号)。

    逐条删除边并重跑最大流，若最大流恰好减少该边的修改容量 w_e，说明任何最大流
    都无法绕开它，它属于某个最小割 → 保留删除；否则恢复。修改容量已“先压损失、
    再压边数”，故删掉的边集就是“总代价最小、边数最少”的最优割。
    """
    removed = [False] * m  # 已确认属于最小割的边
    flow0 = dinic(adj, to, make_caps(removed, W, m), n)
    flow = flow0
    ans: list[int] = []
    for i in range(m):
        removed[i] = True
        nxt = dinic(adj, to, make_caps(removed, W, m), n)
        drop_full = flow - nxt == W[i]  # 恰好损失自己的容量：e 属于最小割
        if drop_full:
            ans.append(i + 1)  # 卡车行号从 1 开始
            flow = nxt
        else:
            removed[i] = False
    return flow0, ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)  # 仓库数 n、卡车数 m（真实数据为 n 在前）
    edges = [(next(data), next(data), next(data)) for _ in range(m)]  # (起点, 终点, 停运损失)

    K = m + 1  # 修改容量的放大系数：任何割的边数都小于 K
    W = [c * K + 1 for _, _, c in edges]  # 修改容量：损失 c 的边变成 c*K+1

    adj: list[list[int]] = [[] for _ in range(n + 1)]
    to = [0] * (2 * m)
    for i, (u, v, _) in enumerate(edges):
        fwd, rev = 2 * i, 2 * i + 1
        to[fwd], to[rev] = v, u
        adj[u].append(fwd)
        adj[v].append(rev)

    flow0, ans = extract_cut_edges(adj, to, n, m, W)
    cost, count = flow0 // K, len(ans)  # 商是最小损失，余数是所选边数
    out = [f"{cost} {count}"] + [str(i) for i in ans]
    print("\n".join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:33
 * update_at: 2026-10-06 11:33
 *
 * main.cpp：追查坏牛奶。
 * 把停运若干卡车使 1 号仓库到不了 n 号仓库建模成带权有向图的最小割，
 * 用容量变换 w_e = c_e * K + 1（K = m + 1）把“损失最小、其次卡车数最少”
 * 两个目标合并成一次最小割，再用 Dinic 求最大流；最后按输入顺序逐条删边
 * 重测流，恰好让最大流下降 w_e 的边就属于该最小割。
 */
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;

const int MAXN = 35;          // 仓库数 n <= 32
const int MAXM = 1005;        // 卡车数 m <= 1000
const int MAXE = 2 * MAXM;    // 每条边带一条反向边
const ll INF = 1000000000000000000LL;

int n;                        // 仓库数（题面第一行的第一个数）
int m;                        // 卡车数（题面第一行的第二个数）
int head[MAXN];               // head[u]：节点 u 的第一条出边编号
int nxt_edge[MAXE];           // 链式前向星的下一条边
int to[MAXE];                 // 边的终点
ll cap[MAXE];                 // 当前残量网络的容量（成对出现：2i 正向，2i+1 反向）
int edge_cnt;                 // 已加入的边数

ll base_w[MAXM];              // base_w[i]：第 i 条卡车线路的修改容量 c*K+1，下标从 0 开始
bool removed[MAXM];           // removed[i]：第 i 条线路是否已被确认属于最小割

int level[MAXN];              // Dinic：BFS 得到的层次
int cur[MAXN];                // Dinic：当前弧指针

// 加入一条有向边以及它的反向边，两者编号为 2i 与 2i+1。
void add_edge(int u, int v, ll c) {
    to[edge_cnt] = v;
    cap[edge_cnt] = c;
    nxt_edge[edge_cnt] = head[u];
    head[u] = edge_cnt;
    edge_cnt++;
}

// 按 removed 标记重建残量网络：被删掉的线路容量为 0，其余取修改容量。
void reset_cap() {
    for (int i = 0; i < 2 * m; i++) {
        cap[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        if (!removed[i]) {
            cap[2 * i] = base_w[i];
        }
    }
}

// Dinic 的 BFS 分层，返回汇点 t 是否可达。
bool bfs(int s, int t) {
    for (int i = 1; i <= n; i++) {
        level[i] = -1;
    }
    level[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int e = head[u]; e != -1; e = nxt_edge[e]) {
            int v = to[e];
            if (cap[e] > 0 && level[v] < 0) {
                level[v] = level[u] + 1;
                q.push(v);
            }
        }
    }
    return level[t] >= 0;
}

// Dinic 的一次增广：沿层次递增的路径把 f 的流量尽量送到汇点，返回实际送出量。
ll dfs(int u, int t, ll f) {
    if (u == t) {
        return f;
    }
    while (cur[u] != -1) {
        int e = cur[u];
        int v = to[e];
        if (cap[e] > 0 && level[v] == level[u] + 1) {
            ll d = dfs(v, t, min(f, cap[e]));
            if (d > 0) {
                cap[e] -= d;
                cap[e ^ 1] += d;
                return d;
            }
        }
        cur[u] = nxt_edge[e];
    }
    return 0;
}

// 在当前残量网络上求 1 号仓库到 n 号仓库的最大流。
ll max_flow() {
    ll flow = 0;
    int s = 1;
    int t = n;
    while (bfs(s, t)) {
        for (int i = 1; i <= n; i++) {
            cur[i] = head[i];
        }
        while (true) {
            ll d = dfs(s, t, INF);
            if (d == 0) {
                break;
            }
            flow += d;
        }
    }
    return flow;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        head[i] = -1;
    }
    edge_cnt = 0;

    ll K = m + 1; // 放大系数：任何割的边数都不超过 m，必小于 K
    for (int i = 0; i < m; i++) {
        int u, v;
        ll c;
        scanf("%d %d %lld", &u, &v, &c);
        base_w[i] = c * K + 1; // 损失 c 的线路容量变成 c*K+1
        add_edge(u, v, 0);     // 容量稍后由 reset_cap 填入，这里先建好边结构
        add_edge(v, u, 0);
        removed[i] = false;
    }

    reset_cap();
    ll total_flow = max_flow(); // 变换后图的最大流 = 最小割值
    ll cur_flow = total_flow;

    int ans[MAXM]; // 属于最小割的线路行号（按输入顺序）
    int ans_cnt = 0;

    // 贪心提取割边：逐条删除并重跑最大流，若最大流恰好下降该边的修改容量，
    // 说明任何最大流都绕不开它，它属于某个最小割。
    for (int i = 0; i < m; i++) {
        removed[i] = true;
        reset_cap();
        ll next_flow = max_flow();
        if (cur_flow - next_flow == base_w[i]) {
            ans[ans_cnt] = i + 1; // 线路行号从 1 开始
            ans_cnt++;
            cur_flow = next_flow;
        } else {
            removed[i] = false;
        }
    }

    ll cost = total_flow / K; // 商是最小总损失
    printf("%lld %d\n", cost, ans_cnt);
    for (int i = 0; i < ans_cnt; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

复杂度

一次 Dinic 最坏 $O(V^2E)$ ，本题 $V=n\leqslant 32$ 、 $E=m\leqslant 1000$ ，实际分层少、单次很快。
贪心阶段对每条边重跑一次最大流，共 $O(m)$ 次，总复杂度 $O(m \cdot V^2E)$ 。实测 12 组官方数据单测最长约 0.27 s。
空间 $O(V+E)$ 。

总结

把“停运卡车防送达”还原成带权有向图的最小割：最大流给出最小割值；容量变换 $w_e=c_e\cdot K+1$ （ $K=m+1$ ）把“代价最小、其次边数最少”两个排序目标合并成一次最小割；最后按输入顺序逐条删边重测最大流，把属于最小割的线路精确挑出来输出。

图示解析

text

1
2
3
4
5
6
7
8
9
10带权有向图 1→n        删边使 1 不可达 n         枚举 2^m / 2^(n-2) 都爆炸
     │                    │                              ▲
     ▼                    ▼                              │
 建模：问题 = 最小割 ──▶ 最大流 = 最小割值 ──► 容量变换 w_e = c_e·K+1 (K=m+1)
     │                                                       │ 新割值 = K·代价 + 边数
     ▼                                                       ▼
 Dinic 求出 F ──────────────────────────────► 贪心：逐条删边重测流，恰好损失 w_e 的边入答案
                                                               │
                                                               ▼
                                        输出 F//K（最小损失）与按输入顺序的行号（最少边数）

从左到右读：建模把删边方案等价成顶点二分（最小割）；变换让一次最大流同时满足 “总代价最小”与“边数最少”两个排序目标；贪心把最小割的每一条边按输入顺序精确找出来，直接输出。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析