欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-08 17:57:15
...

传送门

仔细读读题发现是二分图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;
}