【TJOI2018】智力竞赛【二分图】【二分答案】

传送门

仔细读读题发现是二分图DAG可重路径。

顺带复习二分图的写法。

我们在增广的时候，不是让妹子去找男朋友，而是让妹子已经有的男朋友去再找一个女朋友。

这样就可以让对方妹子孤单凄冷，然后你就趁虚而入了……喜闻乐见地匹配了。

所以我们不需要真的复制一遍点，只需要每次让对方指向自己就行。

然后就是点数-最大匹配了。

 

对于这道题而言，两个子任务。

判断是否可以覆盖全图。

如果不能，求出不被覆盖的点权最小值的最大值。

这一看又是二分答案。

二分我们的答案，答案以下的点都要被覆盖。所以每次run一遍，看看是否满足那个公式就行。

用floyd求传递闭包。

#include<bits/stdc++.h>
using namespace std;
#define in read()
int in{
	int cnt=0,f=1;char ch=0;
	while(!isdigit(ch)){
		ch=getchar();if(ch=='-')f=-1;
	}
	while(isdigit(ch)){
		cnt=cnt*10+ch-48;
		ch=getchar();
	}return cnt*f;
}
int G[503][503],g[503][503];
int n,m,key[503],b[503],bcnt;
int vis[503],match[503];
bool find(int u){
	for(int i=1;i<=m;i++){
		if(g[u][i]&&!vis[i]){
			vis[i]=1;
			if(match[i]==-1||find(match[i])){
				match[i]=u;return true;
			}
		}
	}return false;
}
bool check(int x){
	int sum=0;
	for(int i=1;i<=m;i++)if(key[i]<x)++sum;//cout<<sum<<" ";
	for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)
	if(key[i]<x&&key[j]<x)g[i][j]=G[i][j];
	else g[i][j]=0;
	memset(match,-1,sizeof(match));
	for(int i=1;i<=m;i++){
		if(key[i]>=x)continue;
		memset(vis,0,sizeof(vis));
		if(find(i))--sum;
	}//cout<<sum<<endl;
	return sum<=n+1;
}
signed main(){
	n=in;m=in;
	for(int i=1;i<=m;i++){
		key[i]=b[i]=in;int x=in;
		for(int j=1;j<=x;j++){
			int y=in;G[i][y]=1;
		}
	}
	sort(b+1,b+m+1);bcnt=unique(b+1,b+m+1)-b-1;
	for(int i=1;i<=m;i++)key[i]=lower_bound(b+1,b+bcnt+1,key[i])-b;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=m;j++){
			if(i==j)continue;
			for(int k=1;k<=m;k++){
				if(i==k||j==k)continue;
				G[j][k]|=G[j][i]&G[i][k];
			}
		}
	}
//	for(int i=1;i<=m;i++){
//		for(int j=1;j<=m;j++)cout<<G[i][j]<<" ";cout<<endl;
//	}
	for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)g[i][j]=G[i][j];
//	cout<<bcnt<<endl;
	if(check(bcnt+1)){
		cout<<"AK";return 0;
	}
	int l=1,r=bcnt;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid))l=mid;
		else r=mid-1;
	}cout<<b[l];
	return 0;
}