---

目录

• [TOC]

题目链接

loj#2574. 「TJOI2018」智力竞赛

题解

就是求可重路径覆盖之后最大化剩余点的最小权值

二分答案后就是一个可重复路径覆盖

处理出可达点做二分图匹配就好了

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#define gc getchar()

#define pc putchar

inline int read() {

	int x = 0,f = 1;

	char c = getchar();

	while(c < '0' || c > '9') c = gc;

	while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = gc;

	return x * f;

}

void print(int x) {

 	if(x < 0) {

 		pc('-');

 		x = -x;

 	}

 	if(x >= 10) print(x / 10);

 	pc(x % 10 + '0');

 }

const int maxn = 507;

int n,m;

bool mp[maxn][maxn];

int val[maxn];

int a[maxn];

void floyd() {

	for(int k = 1;k <= n;++ k)

		for(int i = 1;i <= n;++ i)

			for(int j = 1;j <= n;++ j)

				mp[i][j] |= mp[i][k] & mp[k][j];

}

int vis[maxn];

int tot = 0;

int bel[maxn];

bool find(int x,int fa) {

	for(int i = 1;i <= tot;++ i) {

		if(vis[i] != fa && mp[a[x]][a[i]]) {

			vis[i] = fa;

			if(!bel[i] || find(bel[i],fa)) {

				bel[i] = x;

				return true;

			}

		}

	}

	return false;

}

int check(int x) {

	tot = 0;

	for(int i = 1;i <= m;++ i) if(val[i] < x) a[++ tot] = i;

	int ret = tot;

	memset(bel,0,sizeof bel);

	for(int i = 1;i <= tot;++ i) {

		if(find(i,i)) ret --;

	}

	return ret;

}

int main() {

	//freopen("contest2.in","r",stdin);

	n = read() + 1, m = read();

	int mx = 0;

	for(int k,i = 1;i <= m;++ i) {

		val[i] = read();

		mx = std::max(mx,val[i]);

		k = read();

		for(int v,j = 1;j <= k;++ j) {

				v = read();

				mp[i][v] = 1;

		}

	}

	floyd();

	int ans = -1;

	int l = 1,r = mx;

	while(l <= r) {

		int mid = l + r >> 1;

		if(check(mid) <= n) l = mid + 1,ans = mid;

		else r = mid - 1;

	}

	if(l <= mx) print(ans),pc('\n');

	else puts("AK");

	return 0;

}