BZOJ

分析

根据要求的东西可以看出是二分答案。因此考虑怎么写 check()

注意到每个学生仅有 $2$ 种选择,因此可以考虑 2-SAT。

对于每一个学生 $i$,枚举所有排名在 $[mid+1,n]$ 内的学生 $j$,并根据两人第一年选的老师连边即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
#define re register
using namespace std;
 
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10,M=4000000+10;

int n,a[N],p[N][N],x[N],y[N];

struct edge { int v,nxt; } e[M];
int head[N],ecnt;
inline void addEdge(int u,int v) {
    e[++ecnt]=(edge){v,head[u]},head[u]=ecnt;
}

int dfn[N],low[N],tim=0,sta[N],in[N],top=0,bl[N],tot=0;
inline void tarjan(int u) {
    dfn[u]=low[u]=++tim,sta[++top]=u,in[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) { int v=e[i].v;
        if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
        else if (in[v]) low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u]) { ++tot;
        while ("longge ak ioi") {
            int t=sta[top--]; in[t]=0,bl[t]=tot;
            if (t==u) break;
        }
    }
}

inline int check(int mid) {
    memset(head,0,sizeof(head)),ecnt=0;
    memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),tim=0;
    memset(in,0,sizeof(in)),top=0;
    memset(bl,0,sizeof(bl)),tot=0;
    for (re int u=1;u<=n;++u) {
        for (re int i=mid+1;i<n;++i) { int v=p[u][i];
            if (x[u]==x[v]) addEdge(u,v+n),addEdge(v,u+n);
            if (x[u]==y[v]) addEdge(u,v),addEdge(v+n,u+n);
            if (y[u]==x[v]) addEdge(u+n,v+n),addEdge(v,u);
            if (y[u]==y[v]) addEdge(u+n,v),addEdge(v+n,u);
        }
    }
    for (re int i=1;i<=n<<1;++i) if (!dfn[i]) tarjan(i);
    for (re int i=1;i<=n;++i) if (bl[i]==bl[i+n]) return 0;
    return 1;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        a[i]=read(); x[i]=a[i]==0?1:0,y[i]=a[i]==2?1:2;
        for (re int j=1;j<n;++j) p[i][j]=read();
    }
    int L=1,R=n-1;
    while (L<R) {
        int mid=(L+R)>>1;
        if (check(mid)) R=mid;
        else L=mid+1;
    }
    printf("%d\n",L);
    return 0;
}
最后修改:2020 年 02 月 26 日 09 : 36 AM