题目大意
给定一个有向无环图，你需要用最少的路径覆盖所有的 边 。每条路径可以从任意点出发，沿着有向边走到无法继续为止。允许重复经过边，但要求路径数最少。输出最少路径数和具体路径。
题目分析
这个问题与经典的“最小路径覆盖（点覆盖）”不同，这里是 边覆盖 。在 DAG\\texttt{DAG}DAG 中，用最少的路径覆盖所有边，等价于求解 有源汇有下界最小流 问题。
关键转化
对原图中的每条边，我们要求它 至少被经过一次 。因此可以为每条边设置一个 下界为 111 ，上界为无穷大的流量。然后求一个最小可行流，其中源点 SSS 连接所有入度为 000 的点，所有出度为 000 的点连接汇点 TTT 。
最少路径数的计算公式
设 in[i]in[i]in[i] 表示节点 iii 的入度，out[i]out[i]out[i] 表示节点 iii 的出度。则最少需要的路径数为：
k=∑imax(0,out[i]−in[i])
k = \\sum_{i} \\max(0, out[i] – in[i])
k=i∑max(0,out[i]−in[i])
若图中所有节点都有 out[i]≤in[i]out[i] \\le in[i]out[i]≤in[i] 但存在边，则 k=1k = 1k=1 。
这个公式可以直接得到答案，但若要输出具体路径，需要网络流构造。
网络流建模
建图
- 对原图的每条有向边 u→vu \\to vu→v，在网络中添加一条边 u→vu \\to vu→v，容量为 ∞\\infty∞（表示可重复经过），下界为 111（必须经过一次）。
处理下界
设 deg[i]=in[i]−out[i]deg[i] = in[i] – out[i]deg[i]=in[i]−out[i] （其中 in[i],out[i]in[i], out[i]in[i],out[i] 为原图度数）。
- 若 deg[i]>0deg[i] > 0deg[i]>0，从超级源点 SSSSSS 向 iii 连容量 deg[i]deg[i]deg[i] 的边。
- 若 deg[i]<0deg[i] < 0deg[i]<0，从 iii 向超级汇点 STSTST 连容量 −deg[i]-deg[i]−deg[i] 的边。
源汇处理
- 设源点 SSS 连接所有 原图入度为 000 的点，容量 ∞\\infty∞。
- 所有 原图出度为 000 的点连接汇点 TTT，容量 ∞\\infty∞。
- 添加 T→ST \\to ST→S 边，容量 ∞\\infty∞。
求解最小流
- 先跑一次 SS→STSS \\to STSS→ST 的最大流，得到可行流。
- 添加 T→ST \\to ST→S 边（若未加）。
- 再跑一次 SS→STSS \\to STSS→ST 的最大流，此时总流量即为最少路径数。
路径输出
在残余网络中，从 SSS 出发沿有流量的边 DFS\\texttt{DFS}DFS ，每条路径输出经过的点序列。
复杂度
节点数 n≤100n \\le 100n≤100，边数最多约 n2=10000n^2 = 10000n2=10000。使用 ISAP\\texttt{ISAP}ISAP 或 Dinic\\texttt{Dinic}Dinic 算法均可通过。时间主要消耗在两次最大流上，复杂度 O(EV)O(E \\sqrt{V})O(EV) 或 O(V2E)O(V^2 E)O(V2E)，实际运行很快。
参考代码
解法一：ISAP\\texttt{ISAP}ISAP 算法
// Inspection
// UVa ID: 1440
// Verdict: Accepted
// Submission Date: 2026-05-28
// UVa Run Time: 0.020s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210;
const int INF = 0x3f3f3f3f;
struct Edge {
int v, cap, nxt;
} edge[MAXN * MAXN];
int head[MAXN], tot;
int dis[MAXN], cur[MAXN], pre[MAXN], gap[MAXN];
int inDeg[MAXN], outDeg[MAXN];
int n, S, T, SS, ST;
void addEdge(int u, int v, int cap) {
edge[tot] = {v, cap, head[u]};
head[u] = tot++;
edge[tot] = {u, 0, head[v]};
head[v] = tot++;
}
void bfs(int t) {
memset(dis, INF, sizeof(dis));
memset(gap, 0, sizeof(gap));
memcpy(cur, head, sizeof(cur));
queue<int> q;
q.push(t);
dis[t] = 0;
gap[0] = 1;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (dis[v] == INF) {
dis[v] = dis[u] + 1;
gap[dis[v]]++;
q.push(v);
}
}
}
}
int ISAP(int s, int t, int nodeCnt) {
bfs(t);
int u = pre[s] = s;
int flow = 0;
while (dis[s] < nodeCnt) {
if (u == t) {
int aug = INF;
int idx = –1;
for (int i = s; i != t; i = edge[cur[i]].v) {
if (aug > edge[cur[i]].cap) {
aug = edge[cur[i]].cap;
idx = i;
}
}
for (int i = s; i != t; i = edge[cur[i]].v) {
edge[cur[i]].cap -= aug;
edge[cur[i] ^ 1].cap += aug;
}
flow += aug;
u = idx;
}
int i;
for (i = cur[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (edge[i].cap && dis[v] + 1 == dis[u]) {
cur[u] = i;
pre[v] = u;
u = v;
break;
}
}
if (i == –1) {
if (—gap[dis[u]] == 0) break;
int md = nodeCnt;
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (edge[i].cap && dis[edge[i].v] < md) {
md = dis[edge[i].v];
cur[u] = i;
}
}
dis[u] = md + 1;
gap[dis[u]]++;
u = pre[u];
}
}
return flow;
}
void init() {
memset(head, –1, sizeof(head));
memset(inDeg, 0, sizeof(inDeg));
memset(outDeg, 0, sizeof(outDeg));
tot = 0;
}
void dfsPath(int u) {
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (i & 1) continue;
if (!edge[i ^ 1].cap) continue;
if (v == S || v == T || v > n) continue;
edge[i ^ 1].cap—;
printf(" %d", v);
dfsPath(v);
break;
}
}
int main() {
while (scanf("%d", &n) == 1) {
init();
S = n + 1, T = n + 2, SS = n + 3, ST = n + 4;
// 读入原图
for (int i = 1; i <= n; i++) {
int m; scanf("%d", &m);
for (int j = 0; j < m; j++) {
int v; scanf("%d", &v);
outDeg[i]++;
inDeg[v]++;
addEdge(i, v, INF);
}
}
// 添加源汇辅助边
for (int i = 1; i <= n; i++) {
if (!outDeg[i]) addEdge(i, T, INF);
if (!inDeg[i]) addEdge(S, i, INF);
int diff = inDeg[i] – outDeg[i];
if (diff > 0) addEdge(SS, i, diff);
else if (diff < 0) addEdge(i, ST, –diff);
}
// 第一次最大流
ISAP(SS, ST, ST + 1);
// 添加 T->S 边
addEdge(T, S, INF);
// 第二次最大流，得到最小路径数
int ans = ISAP(SS, ST, ST + 1);
printf("%d\\n", ans);
// 构造路径
// 恢复每条边的下界流量
for (int u = 1; u <= n; u++) {
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (i & 1) continue;
int v = edge[i].v;
if (v == S || v == T) continue;
edge[i ^ 1].cap++;
}
}
// 从 S 出发找所有路径
for (int i = head[S]; ~i; i = edge[i].nxt) {
if (i & 1) continue;
while (edge[i ^ 1].cap) {
edge[i ^ 1].cap—;
int v = edge[i].v;
printf("%d", v);
dfsPath(v);
printf("\\n");
}
}
}
return 0;
}
解法二：Dinic\\texttt{Dinic}Dinic 算法
// Inspection
// UVa ID: 1440
// Verdict: Accepted
// Submission Date: 2026-05-28
// UVa Run Time: 0.020s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210;
const int INF = 1e8;
struct Edge {
int v, cap, nxt;
} edge[MAXN * MAXN];
int head[MAXN], tot;
int inDeg[MAXN], outDeg[MAXN];
int level[MAXN], cur[MAXN];
int n, S, T, SS, ST;
void init() {
memset(head, –1, sizeof(head));
memset(inDeg, 0, sizeof(inDeg));
memset(outDeg, 0, sizeof(outDeg));
tot = 0;
}
void addEdge(int u, int v, int cap) {
edge[tot] = {v, cap, head[u]};
head[u] = tot++;
edge[tot] = {u, 0, head[v]};
head[v] = tot++;
}
bool bfs(int s, int t) {
memset(level, –1, sizeof(level));
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (level[v] == –1 && edge[i].cap > 0) {
level[v] = level[u] + 1;
q.push(v);
}
}
}
return level[t] != –1;
}
int dfs(int u, int t, int f) {
if (u == t || f == 0) return f;
int flow = 0;
for (int &i = cur[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (level[v] == level[u] + 1 && edge[i].cap > 0) {
int pushed = dfs(v, t, min(f, edge[i].cap));
if (pushed) {
edge[i].cap -= pushed;
edge[i ^ 1].cap += pushed;
flow += pushed;
f -= pushed;
if (f == 0) break;
}
}
}
return flow;
}
int dinic(int s, int t) {
int flow = 0;
while (bfs(s, t)) {
memcpy(cur, head, sizeof(head));
flow += dfs(s, t, INF);
}
return flow;
}
void dfsPath(int u) {
for (int i = head[u]; ~i; i = edge[i].nxt) {
int v = edge[i].v;
if (i & 1) continue;
if (edge[i ^ 1].cap == 0) continue;
if (v == S || v == T || v > n) continue;
edge[i ^ 1].cap—;
printf(" %d", v);
dfsPath(v);
break;
}
}
int main() {
while (scanf("%d", &n) == 1) {
init();
S = n + 1, T = n + 2, SS = n + 3, ST = n + 4;
// 读入原图
for (int i = 1; i <= n; i++) {
int m; scanf("%d", &m);
for (int j = 0; j < m; j++) {
int v; scanf("%d", &v);
outDeg[i]++;
inDeg[v]++;
addEdge(i, v, INF);
}
}
// 添加源汇辅助边
for (int i = 1; i <= n; i++) {
if (!outDeg[i]) addEdge(i, T, INF);
if (!inDeg[i]) addEdge(S, i, INF);
int diff = inDeg[i] – outDeg[i];
if (diff > 0) addEdge(SS, i, diff);
else if (diff < 0) addEdge(i, ST, –diff);
}
// 第一次最大流
dinic(SS, ST);
// 添加 T->S 边
addEdge(T, S, INF);
// 第二次最大流
int ans = dinic(SS, ST);
printf("%d\\n", ans);
// 恢复每条边的下界流量
for (int u = 1; u <= n; u++) {
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (i & 1) continue;
int v = edge[i].v;
if (v == S || v == T) continue;
edge[i ^ 1].cap++;
}
}
// 输出路径
for (int i = head[S]; ~i; i = edge[i].nxt) {
if (i & 1) continue;
while (edge[i ^ 1].cap) {
edge[i ^ 1].cap—;
int v = edge[i].v;
printf("%d", v);
dfsPath(v);
printf("\\n");
}
}
}
return 0;
}
总结
本题的核心是将“每条边至少经过一次”转化为 有下界的流量 ，通过两次最大流（可行流 + 退流）得到最小路径数。输出路径时利用残余网络 DFS\\texttt{DFS}DFS 即可。两种最大流算法（ISAP\\texttt{ISAP}ISAP 和 Dinic\\texttt{Dinic}Dinic）均能通过，读者可根据习惯选择。
