> 求解无权 DAG 的最小路径**边**覆盖。特别的，路径可以重复走。
很神奇一道题。神奇在我在 check 自己的 Sol 的时候发现了这么一回事：
> 对于图中的每个点 $i$，设 $d_i$ 为( $i$ 的入度 - $i$ 的出度)的值，按照 $d_i$将图中的点分类：
>
> $d_i<0$ 的称为“入少出多”的点，$d_i>0$ 的称为“出少入多”的点，$d_i=0$ 的称为“入出相等”的点。则有：
>
> > 定理：有向无环图中最小边路径覆盖的值等于图中所有“入少出多”的点的 $d_i$ 绝对值之和。
这还是比较显然的，注意到这个定理是在陈述「边覆盖」就不难理解了。 然后借此先说 Sol 1:
### Sol 1
考虑本题和不能重复走的最小路径覆盖有什么区别，那必然是存在一些路径可以重复经过。我断言，这样的路径必然满足起点 $d_i>0$，终点的 $d_i<0$ ，否则没有必要重复经过。考虑某条这样的路径 $(s:t)$ 每被重复经过一次，就必然是为了将 $t$ 之后的某条路经和 $s$ 之前的某条路径拼插起来，这样原来需要 $2$ 次现在就只需要 $1$ 次。
于是考虑直接对着这个跑一次最大流即可，各个地方的流量都是 $1$ ，拿定理中的答案减去这个最大流就好了。
### Sol 2
…发现这题就是一个带下界的最小流。于是就跑一个带下界的最小流即可。
具体的，就是发现每条边都必须要至少跑一次。那么就是一条 $\rm lower=1,upper=1$ 的边。随便连一下源点汇点跑一个最小流就好了。
输出方案。考虑输出方案就只需要按照流过的边 `dfs` 即可。不难知道这样是对的。
我写的是 Sol2 里的代码，因为最近正在复习上下界。
~~ISAP即是真理，Dinic需要清除~~
不过感觉显然 Sol2 无聊了好几倍啊？
```cpp
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
const int N = 200010 ;
const int M = 300010 ;
const int Inf = 1000000007 ;
using namespace std ;
template <typename T>
void debug(T x, char c = '\n'){ cerr << x << c ; }
template <typename T>
void debug(T *const tp, int minn, int maxn, char v = ' ', char c = '\n'){
for (int i = minn ; i <= maxn ; ++ i) debug(tp[i], v) ; cerr << c ;
}
typedef long long ll ;
void chkmin(int &x, int t){ x = x < t ? x : t ; }
void chkmin(ll &x, ll t){ x = x < t ? x : t ; }
namespace ISAP{
#define to(k) e[k].to
#define cap(k) e[k].cap
#define cost(k) e[k].cost
#define from(k) e[k].from
#define flow(k) e[k].flow
struct edge{
int from ;
ll flow ;
ll cap ;
int to ;
edge (int a = 0, int b = 0, ll c = 0){
from = a, to = b, cap = c, flow = 0 ;
}
} e[M] ;
int n ;
ll ans ;
int cnt ;
int S, T ;
int h, t ;
int que[N] ;
int pre[N] ;
int hgt[N] ;
int cur[N] ;
int gap[N] ;
vector <int> E[N] ;
void add(int x, int y, ll c){
e[++ cnt] = edge(x, y, c) ; E[x].push_back(cnt) ;
e[++ cnt] = edge(y, x, 0) ; E[y].push_back(cnt) ;
}
void reset(int x, int y, int z){
memset(cur, 0, sizeof(cur)) ;
memset(hgt, 0, sizeof(hgt)) ;
memset(gap, 0, sizeof(gap)) ;
S = x, T = y, n = z ; cnt = -1 ;
for (int i = 1 ; i <= n ; ++ i) E[i].clear() ;
}
void prebfs(){
que[h = t = 1] = T ;
while (h <= t){
int x = que[h ++] ;
for (auto k : E[x])
if (!hgt[to(k)] && to(k) != T)
hgt[que[++ t] = to(k)] = hgt[x] + 1 ;
}
for (int i = 1 ; i <= n ; ++ i) gap[hgt[i]] ++ ;
}
void Aug(){
int x = T ;
ll z = 1ll << 60 ;
while (x != S){
chkmin(z, cap(pre[x]) - flow(pre[x])) ;
x = from(pre[x]) ;
}
ans += z ; x = T ;
while (x != S){
flow(pre[x]) += z ;
flow(pre[x] ^ 1) -= z ;
x = from(pre[x]) ;
}
}
bool Advance(int x, int &y){
bool ret = 0 ;
for (int d = cur[x] ; d < E[x].size() ; ++ d){
int k = E[x][d] ;
if (flow(k) >= cap(k)) continue ;
if (hgt[x] != hgt[to(k)] + 1) continue ;
cur[x] = d ; ret = 1 ;
pre[y = to(k)] = k ; break ;
}
return ret ;
}
void isap(){
int x = S ;
for (int i = 1 ; i <= n ; ++ i)
hgt[i] = gap[i] = 0 ; prebfs() ;
while (hgt[S] < n){
// cout << x << '\n' ;
if (x == T)
Aug(), x = S ;
if (!Advance(x, x)){
int minh = n - 1 ;
for (auto k : E[x])
if (flow(k) < cap(k))
chkmin(minh, hgt[to(k)]) ;
if (!-- gap[hgt[x]]) return ;
gap[hgt[x] = minh + 1] ++ ; cur[x] = 0 ;
if (x != S) x = from(pre[x]) ;
}
}
}
}
namespace YES_Lower_Upper_Minimum{
using namespace :: ISAP ;
void add_e(int x, int y, int c1, int c2){
// cout << x << " " << y << " " << c1 << " " << c2 << '\n' ;
add(S, y, c1) ; add(x, T, c1) ; add(x, y, c2 - c1) ;
}
void solve(int s, int t){
isap() ; //puts("%%%%");//debug(ans) ;
add_e(t, s, 0, Inf), ans = 0 ;
isap() ; cout << ans << "\n" ;
}
void do_back(int o){
for (int i = 0 ; i <= cnt ; ++ i)
if (from(i) <= o && to(i) <= o && cap(i) > 0) ++ flow(i) ;
}
bool _space ;
void dfs(int x, int o){
if (!_space)
putchar(' ') ;
else _space = 0 ;
cout << x ;
for (auto k : E[x])
if (to(k) <= o && flow(k) > 0){
flow(k) --, dfs(to(k), o) ; break ;
}
}
void do_(int s, int o){
while (ans){
for (auto k : E[s]){
if (to(k) <= o){
if (flow(k)){
_space = 1 ;
-- flow(k), -- ans ;
dfs(to(k), o), puts("") ;
}
}
}
}
}
}
int n, m, s, t ;
using ISAP :: reset ;
using YES_Lower_Upper_Minimum :: do_ ;
using YES_Lower_Upper_Minimum :: dfs ;
using YES_Lower_Upper_Minimum :: add_e ;
using YES_Lower_Upper_Minimum :: solve ;
using YES_Lower_Upper_Minimum :: do_back ;
int main(){
int x, y, i ;
while (scanf("%d", &n) == 1){
s = n + 1, t = n + 2 ;
reset(t + 1, t + 2, t + 2) ;
for (x = 1 ; x <= n ; ++ x){
scanf("%d", &i) ;
while (i --){
scanf("%d", &y) ;
add_e(x, y, 1, Inf) ;
}
add_e(s, x, 0, Inf) ;
add_e(x, t, 0, Inf) ;
}
solve(s, t) ;
do_back(n) ;
do_(s, n) ;
}
return 0 ;
}
```