Solution
我们可以贪心的考虑，就是尽量把小的覆盖完。我们把所有的点从小到大排序，然后直接二分覆盖前(k)个点，用网络流跑一下二分图求出最小链覆盖，然后就判断一下点数减去最小链有没有超过给定的人数
由于这道题的链可以重叠的，所以我们可以直接求出每一个点可达的所有点。然后拆点，对于每一个点和其可达的点，从左边的点连向右边的点。然后需要的最小链的数量就是总点数减去总流量
Code
#include <bits/stdc++.h>
using namespace std;
#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef pair<int, int> pii;
inline int read() {
int sum = 0, fg = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') fg = -1;
for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
return fg * sum;
}
const int maxn = 500 + 10;
const int maxm = 5e5 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
namespace Dinic {
int S, T;
int Begin[maxn << 1], Next[maxm + (maxn << 2)], To[maxm + (maxn << 2)], w[maxm + (maxn << 2)], e;
int d[maxn << 1], cur[maxn << 1];
void init() {
S = 0, T = m << 1 | 1, e = -1;
memset(Begin, -1, sizeof Begin);
}
void add(int x, int y) {
To[++e] = y, Next[e] = Begin[x], Begin[x] = e, w[e] = 1;
To[++e] = x, Next[e] = Begin[y], Begin[y] = e, w[e] = 0;
}
int bfs() {
memset(d, 0, sizeof d); d[S] = 1;
queue<int> q; q.push(S);
while (!q.empty()) {
int now = q.front(); q.pop();
for (int i = Begin[now]; i + 1; i = Next[i]) {
int son = To[i];
if (!d[son] && w[i] > 0) {
d[son] = d[now] + 1; q.push(son);
}
}
}
return d[T];
}
int dfs(int now, int flow) {
if (now == T) return flow;
int sum = 0;
for (int &i = cur[now]; i + 1; i = Next[i]) {
int son = To[i];
if (w[i] > 0 && d[son] == d[now] + 1) {
int l = dfs(son, min(flow, w[i]));
if (l) {
w[i] -= l, w[i ^ 1] += l;
flow -= l, sum += l;
if (!flow) break;
}
}
}
return sum;
}
int solve() {
for (int i = 1; i <= m; i++) add(S, i), add(i + m, T);
int ans = 0;
while (bfs()) {
for (int i = S; i <= T; i++) cur[i] = Begin[i];
ans += dfs(S, inf);
}
return ans;
}
}
struct node {
int x, id;
bool operator < (const node &t) const { return x < t.x; }
}A[maxn];
bool b[maxn][maxn];
bool check(int pos) {
Dinic::init();
for (int i = 1; i <= pos; i++)
for (int j = 1; j <= pos; j++) {
int x = A[i].id, y = A[j].id;
if (i == j || !b[x][y]) continue;
Dinic::add(x, y + m);
}
int res = Dinic::solve();
return (pos - res) <= n;
}
int main() {
#ifdef xunzhen
freopen("comp.in", "r", stdin);
freopen("comp.out", "w", stdout);
#endif
n = read() + 1, m = read();
for (int i = 1; i <= m; i++) {
b[i][i] = 1; A[i] = (node){read(), i};
int k = read();
for (int j = 1; j <= k; j++) b[i][read()] = 1;
}
for (int k = 1; k <= m; k++)
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++)
b[i][j] |= b[i][k] & b[k][j];
sort(A + 1, A + m + 1);
int l = 1, r = m;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid + 1;
else r = mid - 1;
}
if (l <= m) printf("%d
", A[l].x);
else puts("AK");
return 0;
}
Summary
第一次做最小链覆盖的题，感觉不是太难，过了样例就直接A了