题解：P4835 [JSOI2014] 学生选课

· · 题解

一道很好的 2-SAT 题。

首先，答案可以二分是显然的，我们先二分答案，这样子就转化为了判定一个 T 是否可行。

每位同学只能从两位老师中选择一个，把每个同学看成一个变量就变成了 2-SAT 问题。而限制就是两个同学之间是否可以同属于一个老师。若不能，则限制了两位同学变量值不能相同，即对于一位老师 p，两位同学 x,y，有 x=p 则 y \ne p，有 y=p 则 x \ne p。

于是我们将每位同学拆成两个点，表示分别属于两个老师。然后依据上面的限制关系，在同学拆成的点之间连边。由于我们二分答案，边是确定的。最后对于每一个 T 我们都能转化为 2-SAT 问题，直接跑模板判定是否可行即可。

下附代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#define int long long
using namespace std;
int n,m,dfn[2000005],low[2000005],tot,bl[2000005],instk[2000005],stk[2000005],top,cnt;
int id[1005][3],c[1005][1005];
vector<int>s[2000005];
void dfs(int x,int fa){
    dfn[x]=low[x]=++tot;stk[++top]=x;instk[x]=1;
    for(int i=0;i<s[x].size();i++){
        int y=s[x][i];
        if(!dfn[y]){
            dfs(y,x);
            low[x]=min(low[x],low[y]);
        }else if(instk[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]){
        cnt++;int k;
        do{
            k=stk[top];top--;
            bl[k]=cnt;instk[k]=0;
        }while(k!=x);
    }
}
bool check(int x){
    tot=0;cnt=0;top=0;
    for(int i=1;i<=2*n;i++) dfn[i]=low[i]=instk[i]=0,s[i].clear(),bl[i]=0;
    for(int i=1;i<=n;i++){
        for(int j=x+1;j<n;j++){
            int y=c[i][j];
            for(int k=0;k<3;k++){
                if(id[i][k]&&id[y][k]){
                    s[id[i][k]].push_back(id[y][k]+(id[y][k]<=n?n:-n));
                    s[id[y][k]].push_back(id[i][k]+(id[i][k]<=n?n:-n));
                }
            }
        }
    }
    for(int i=1;i<=2*n;i++) if(!dfn[i]) dfs(i,0);
    for(int i=1;i<=n;i++){
        if(bl[i]==bl[i+n]) return 0;
    }
    return 1;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,idd=i;cin>>x;
        for(int j=0;j<3;j++){
            if(j!=x) id[i][j]=idd,idd+=n;
        }
        for(int j=1;j<n;j++) cin>>c[i][j];
    }
    int l=1,r=n,cur=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)) cur=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<cur<<endl;
    return 0;
}