TJOI2018 智力竞赛

这题做的真的让我没了智力...

题目大意：
从n个点的图中选出n + 1条链问是否能够全部覆盖（可相交），如果不能，输出覆盖的最小点权最小值最大是多少？

思路：
最小值最大问题考虑二分，二分答案用二分图匹配去求链覆盖即可，记得floyd处理闭包。

吐槽：
调了半天发现是二分上界太大...wtf？

Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 510;
const int INF = 1e9;
int v[MAXN];
int f[MAXN][MAXN];
int match[MAXN];
int a[MAXN];
int l;
int m;
int cnt;
int n;
int ans;
int mx;
int vis[MAXN];
int mk[MAXN][MAXN];
int r;
int read () {
	int q=0,f=1;char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		q=q*10+ch-'0';ch=getchar();
	}
	return q*f;
}
int dfs(int x) {
	for(int i = 1;i <= cnt; ++i) {
		if(!vis[i] and mk[a[x]][a[i]]) {
			vis[i] = 1;
			if(!match[i] or dfs(match[i])) {
				match[i] = x;
				return true;
			}
		}
	}
	return false;
}

int ok(int mid) {
	cnt = 0;
	for(int i = 1;i <= m; ++i) {
		if(v[i] < mid) a[++cnt] = i;
	}
	int res = cnt;
	for(int i = 1;i <= cnt; ++i) {
		memset(vis,0,sizeof vis);
		res -= dfs(i);
	}
	return res;
}
void floyd() {
	for(int k = 1;k <= m; ++k) {
		for(int i = 1;i <= m; ++i) {
			for(int j = 1;j <= m; ++j) {
				mk[i][j] |= mk[i][k] & mk[k][j];
			}
		}
	}
}
int main () {
	n = read(),m = read();
	 ++ n;
	for(int i = 1;i <= m; ++i) {
		v[i] = read();int tmp = read();
		mx = max(mx,v[i]);
		for(int j = 1;j <= tmp; ++j) {
			int x = read();
			mk[i][x] = 1;
		}
	}
	floyd();
	l = 1;
	r = mx;
	ans = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		memset(match,0,sizeof match);
		if(ok(mid) <= n) {
			l = mid + 1;
			ans = mid;
		}
		else r = mid - 1;
	}
	if(ans >= mx) puts("AK");
	else printf("%d\n",ans);
	return 0;
}