标签：

「JSOI2014」学生选课

传送门
看到这题首先可以二分。
考虑对付当前的 \(mid\) 如何 \(\text{check}\)
我们用 \(f_{i,j}\) 来暗示 \(i\) 对 \(j\) 的好感度排名，那么对付两小我私家 \(i\)，\(j\) 如果有 \(\max\{f_{i, j}, f_{j, i}\} > mid\) 那么显然这两小我私家是不能上同一个老师的课的。
而且每小我私家可以上的课只有两种，，我们记为 \(a_{i, 0 / 1}\)
假设 \(i\)，\(j\) 对付当前的 \(mid\) 而言不能分在一起，此中 \(a_{i, 0} = a_{j, 0}\)，那么我们可以发明：

\(i\) 上 \(a_{i, 0}\) 的课，则必需有 \(j\) 上 \(a_{j, 1}\) 的课

\(j\) 上 \(a_{j, 0}\) 的课，则必需有 \(i\) 上 \(a_{i, 1}\) 的课

可以发明这就是一个裸的 \(\text{2-SAT}\)
所以我们每次 \(\text{check}\) 都建图跑一遍 \(\text{2-SAT}\) 就好了。
参考代码：

#include <cstring> #include <cstdio> #define rg register #define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout) template < class T > inline T min(T a, T b) { return a < b ? a : b; } template < class T > inline T max(T a, T b) { return a > b ? a : b; } template < class T > inline void read(T& s) { s = 0; int f = 0; char c = getchar(); while ('0' > c || c > '9') f |= c == '-', c = getchar(); while ('0' <= c && c <= '9') s = s * 10 + c - 48, c = getchar(); s = f ? -s : s; } const int _ = 1010; int tot, head[_ * 3]; struct Edge { int v, nxt; } edge[_ * _ * 4]; inline void Add_edge(int u, int v) { edge[++tot] = (Edge) { v, head[u] }, head[u] = tot; } int n, t[_], a[_][2], f[_][_]; int num, dfn[_ * 3], low[_ * 3], col, co[_ * 3], top, stk[_ * 3]; inline void tarjan(int u) { dfn[u] = low[u] = ++num, stk[++top] = u; for (rg int i = head[u]; i; i = edge[i].nxt) { int v = edge[i].v; if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]); else if (!co[v]) low[u] = min(low[u], dfn[v]); } if (low[u] == dfn[u]) { ++col; do co[stk[top]] = col; while (stk[top--] != u); } } inline int id(int x, int y) { return y * (n + 1) + x; } inline void init() { tot = num = col = top = 0; memset(head, 0, sizeof head); memset(dfn, 0, sizeof dfn); memset(low, 0, sizeof low); memset(co, 0, sizeof co); } inline bool check(int mid) { init(); for (rg int i = 1; i <= n; ++i) for (rg int j = i + 1; j <= n; ++j) { if (f[i][j] <= mid) continue ; if (a[i][0] == a[j][0]) { Add_edge(id(i, a[i][0]), id(j, a[j][1])); Add_edge(id(j, a[j][0]), id(i, a[i][1])); } if (a[i][0] == a[j][1]) { Add_edge(id(i, a[i][0]), id(j, a[j][0])); Add_edge(id(j, a[j][1]), id(i, a[i][1])); } if (a[i][1] == a[j][0]) { Add_edge(id(i, a[i][1]), id(j, a[j][1])); Add_edge(id(j, a[j][0]), id(i, a[i][0])); } if (a[i][1] == a[j][1]) { Add_edge(id(i, a[i][1]), id(j, a[j][0])); Add_edge(id(j, a[j][1]), id(i, a[i][0])); } } for (rg int i = 1; i <= n; ++i) for (rg int k = 0; k < 3; ++k) if (t[i] != k && !dfn[id(i, k)]) tarjan(id(i, k)); for (rg int i = 1; i <= n; ++i) if (co[id(i, a[i][0])] == co[id(i, a[i][1])]) return 0; return 1; } int main() { #ifndef ONLINE_JUDGE file("cpp"); #endif read(n); for (rg int i = 1; i <= n; ++i) { read(t[i]); if (t[i] == 0) a[i][0] = 1, a[i][1] = 2; if (t[i] == 1) a[i][0] = 0, a[i][1] = 2; if (t[i] == 2) a[i][0] = 0, a[i][1] = 1; for (rg int x, j = 1; j < n; ++j) read(x), f[i][x] = j; } for (rg int i = 1; i <= n; ++i) for (rg int j = i + 1; j <= n; ++j) f[i][j] = max(f[i][j], f[j][i]); 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; }

「JSOI2014」学生选课