题目链接：传送门 求一个DAG的最小边覆盖
无源汇上下界可行流 的板子题 过几天再来写做法 留坑…
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <complex> #include <algorithm> #include <climits> #include <queue> #include <map> #include <set> #include <vector> #include <iomanip> #define A 1000010 #define B 2010 using namespace std; typedef long long ll; const int inf = 1e9 + 7; struct node { int next, to, w; }e[A]; int head[A], num = 1; void add(int fr, int to, int w) { e[++num].next = head[fr]; e[num].to = to; e[num].w = w; head[fr] = num; swap(fr, to); e[++num].next = head[fr]; e[num].to = to; e[num].w = 0; head[fr] = num; } int dep[A], vis[A], S, T, n, in[A], out[A], cur[A], a, b; bool bfs() { memset(dep, 0x3f, sizeof dep); memset(vis, 0, sizeof vis); queue<int> q; q.push(S); dep[S] = 0; while (!q.empty()) { int fr = q.front(); q.pop(); vis[fr] = 0; for (int i = head[fr]; i; i = e[i].next) { int ca = e[i].to; if (e[i].w and dep[ca] > dep[fr] + 1) { dep[ca] = dep[fr] + 1; if (!vis[ca]) { vis[ca] = 1; q.push(ca); } } } } return dep[T] != 0x3f3f3f3f; } int dfs(int fr, int flow, int now = 0) { if (fr == T) return flow; for (int &i = cur[fr]; i; i = e[i].next) { int ca = e[i].to; if (e[i].w and dep[ca] == dep[fr] + 1) { now = dfs(ca, min(e[i].w, flow)); if (now) { e[i].w -= now; e[i ^ 1].w += now; return now; } } } return 0; } int dinic(int ans = 0) { while (bfs()) { memcpy(cur, head, sizeof head); while (int t = dfs(S, 0x3f3f3f3f)) ans += t; } return ans; } int main(int argc, char const *argv[]) { cin >> n; S = 0; T = n + 1; int SS = n + 2, TT = n + 3; for (int i = 1; i <= n; i++) { cin >> a; while (a--) { cin >> b; add(i, b, inf); in[b]++; in[i]--; } } for (int i = 1; i <= n; i++) add(S, i, inf), add(i, T, inf); for (int i = 1; i <= n; i++) if (in[i] > 0) add(SS, i, in[i]); else if (in[i] < 0) add(i, TT, -in[i]); int ans = 0; add(T, S, inf); int Ts = S, Tt = T; S = SS, T = TT; dinic(); ans = e[num].w; e[num].w = e[num ^ 1].w = 0; for (int i = head[SS]; i; i = e[i].next) e[i].w = e[i ^ 1].w = 0; for (int i = head[TT]; i; i = e[i].next) e[i].w = e[i ^ 1].w = 0; S = Tt; T = Ts; cout << ans - dinic() << endl; }