题解：P4835 [JSOI2014] 学生选课

xzy_AK_IOI · 2026-04-25 10:06:56 · 题解

思路分析

简单 2-SAT。

通过这种两个学生不能分配到一个老师容易知道使用 2-SAT。

由于直接做不知道哪些边要连，考虑二分答案。

具体地，令现在二分到的答案为 T。

我们知道所有点（同学）的 T+1 \sim n-1 好感度的点是不能为同一个权值（老师）的，我们又知道一个点的权值只可能有两种，因为规定了不能和初始的老师一样，然后分几类情况分别连边，在套用 2-SAT 的板子即可。

时间复杂度 \mathcal{O(n^2 \log n)}。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define lli long long
#define ull unsigned long long
#define db long double
#define F(i,k,n) for (int i=k;i<=n;i++)
#define R(i,k,n) for (int i=k;i>=n;i--)
#define pu push_back
#define mpr make_pair
#define ins insert
#define lowb(x) (x&(-x))
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)
#define mes(a,b) memset(a,b,sizeof a)
const int N=2e3+10;
const int M=22;
const int mod=1e9+7;
const int inf=1e18;
vector<int>e[N];
int n;
int b[N];
int a[N][N];
int gett[N][2];
int dfn[N],low[N];
int top,cnt,td;
bool ins[N];
int st[N],scc[N];
void tarjan(int u){
    td++;
    top++;
    st[top]=u;
    ins[u]=1;
    dfn[u]=low[u]=td;
    F(i,0,(int)e[u].size()-1){
        int v=e[u][i];
        if (!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if (ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if (low[u]==dfn[u]){
        cnt++;
        while (st[top]!=u){
            scc[st[top]]=cnt;
            ins[st[top]]=0;
            top--;
        }
        scc[st[top]]=cnt;
        ins[st[top]]=0;
        top--;
    }
}
bool check(int mid){
    F(i,1,n){
        e[i].clear(),e[i+n].clear();
    }
    F(i,1,n){
        F(j,mid+1,n-1){
            if (gett[i][0]==gett[a[i][j]][0] && gett[i][1]==gett[a[i][j]][1]){
                e[i].pu(a[i][j]+n);
                e[a[i][j]+n].pu(i);
                e[i+n].pu(a[i][j]);
                e[a[i][j]].pu(i+n);
            }
            else if (gett[i][0]==gett[a[i][j]][1]){
                e[i].pu(a[i][j]);
                e[a[i][j]+n].pu(i+n);
            } 
            else if (gett[i][1]==gett[a[i][j]][0]){
                e[i+n].pu(a[i][j]+n);
                e[a[i][j]].pu(i);
            }  
            else if (gett[i][0]==gett[a[i][j]][0]){
                e[i].pu(a[i][j]+n);
                e[a[i][j]].pu(i+n);
            }
            else if (gett[i][1]==gett[a[i][j]][1]){
                e[i+n].pu(a[i][j]);
                e[a[i][j]+n].pu(i);
            }
//          else{
//              cout<<gett[i][0]<<' '<<gett[i][1]<<' '<<gett[a[i][j]][0]<<' '<<gett[a[i][j]][1]<<'\n';
//          }
        }
    }
    cnt=td=0;
    F(i,1,n) dfn[i]=low[i]=dfn[i+n]=low[i+n]=0,ins[i]=ins[i+n]=0;
    F(i,1,2*n){
        if (!dfn[i]) tarjan(i);
    }
    F(i,1,n){
        if (scc[i]==scc[i+n]) return 0;
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    F(i,1,n){
        cin>>b[i];
        if (b[i]==0){
            gett[i][0]=1;
            gett[i][1]=2;
        }
        else if (b[i]==1){
            gett[i][0]=0;
            gett[i][1]=2;
        }
        else{
            gett[i][0]=0;
            gett[i][1]=1;
        }
        F(j,1,n-1) cin>>a[i][j];
    }
    int l=0,r=n,mid;
    while (l+1!=r){
        mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid;
    }
//  F(i,1,n-1){
//      cout<<check(i);
//  }
    cout<<r;
    return 0;
}