BZOJ5335: [TJOI2018]智力竞赛【二分+二分图匹配】

5335: [TJOI2018]智力竞赛

【题目描述】

传送门

【题解】

带权最长链覆盖,二分最小值即可以。

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN=505;
int n,m,Ans,tim,vis[MAXN],grl[MAXN],a[MAXN],MI[MAXN],G[MAXN][MAXN];
struct Edge{
    int tot,lnk[MAXN],nxt[MAXN*MAXN],son[MAXN*MAXN];
    void clean(){memset(lnk,0,sizeof(lnk));tot=0;}
    void Add(int x,int y){nxt[++tot]=lnk[x];lnk[x]=tot;son[tot]=y;}
}E;
bool Fnd(int x){
    for(int j=E.lnk[x];j;j=E.nxt[j])
    if(vis[E.son[j]]!=tim){
        vis[E.son[j]]=tim;
        if(grl[E.son[j]]==0||Fnd(grl[E.son[j]])){grl[E.son[j]]=x;return 1;}
    }
    return 0;
}
bool check(int x){
    int Now=0;E.clean();
    for(int i=1;i<=n;i++) Now+=(a[i]<x),vis[i]=grl[i]=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) if(a[i]<x&&a[j]<x&&G[i][j]) E.Add(i,j);
    tim=0;
    for(int i=1;i<=n;i++) if(a[i]<x) tim++,Now-=Fnd(i);
    return Now<=m+1;
}
int main(){
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++){
        int k;scanf("%d%d",&a[i],&k);
        for(int j=1;j<=k;j++){
            int x;scanf("%d",&x);G[i][x]=1;
        }
    }
    for(int k=1;k<=n;k++)
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) G[i][j]|=G[i][k]&&G[k][j];
    if(check(1000000001)){printf("AK\n");return 0;}
    for(int L=0,R=1000000000,mid=(R-L>>1)+L;L<=R;mid=(R-L>>1)+L)
    if(check(mid)) Ans=mid,L=mid+1;else R=mid-1;
    printf("%d\n",Ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部