题解
二分答案
求最小路径点覆盖
由于这里最小路径点覆盖，点是可重的，用floyd求出传递闭包（也就是求出，哪两点之间是可达的）
最后用这个floyd求出的数组建出一个新图，在这个图上跑普通的最小路径点覆盖即可
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#define enter putchar('\n')
#define space putchar(' ')
#define MAXN 1000005
//#define ivorysi
#define pb push_back
#define mo 1000007
#define pii pair<int,int>
#define mp make_pair
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 - '0' + c;
c = getchar();
}
res = res * f;
}
template<class T>
void out(T x) {
if(x < 0) {x = -x;putchar('-');}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
int N,M,w[505],f[505][505],d[505][505],num[505];
struct node {
int to,next;
}E[2000005];
int sumE,head[505],matk[505];
bool vis[505];
bool match(int u) {
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(!vis[v]) {
vis[v] = 1;
if(!matk[v] || match(matk[v])) {
matk[v] = u;
return true;
}
}
}
return false;
}
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
bool check(int mid) {
for(int i = 1 ; i <= M ; ++i) {
if(w[i] >= mid) continue;
for(int j = 1 ; j <= M ; ++j) {
if(w[j] >= mid) continue;
d[i][j] = f[i][j];
}
}
for(int k = 1 ; k <= M ; ++k) {
for(int i = 1 ; i <= M ; ++i) {
for(int j = 1 ; j <= M ; ++j) {
d[i][j] |= d[i][k] & d[k][j];
}
}
}
int res = 0;
memset(head,0,sizeof(head));sumE = 0;
for(int i = 1 ; i <= M ; ++i) {
if(w[i] < mid) ++res;
else continue;
for(int j = 1 ; j <= M ; ++j) {
if(d[i][j]) add(i,j);
}
}
if(res <= N) return true;
memset(matk,0,sizeof(matk));
for(int i = 1 ; i <= M ; ++i) {
if(w[i] >= mid) continue;
memset(vis,0,sizeof(vis));
if(match(i)) --res;
}
return res <= N;
}
void Solve() {
read(N);read(M);
++N;
for(int i = 1 ; i <= M ; ++i) {
read(w[i]);
num[i] = w[i];
int k;read(k);
for(int j = 1 ; j <= k ; ++j) {
int v;read(v);
f[i][v] = 1;
}
}
sort(num + 1,num + M + 1);
int L = 1,R = M + 1;
while(L < R) {
int mid = (L + R + 1) >> 1;
if(check(num[mid])) L = mid;
else R = mid - 1;
}
if(R == M + 1) puts("AK");
else {out(num[R]);enter;}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Solve();
}