题解 CF587D 【Duff in Mafia】

> [CF587D Duff in Mafia](https://codeforces.com/contest/587/problem/D) ## 题意 - 给定一张 $n$ 个点 $m$ 条边的无向图，每条边有一个颜色 $c$ 和权值 $t$。 - 你要选出一些边，使得它们是一个**匹配**，同时剩下的边每种颜色也是一个**匹配**。 - 同时，你要最小化选出的边的最大权值。 - $n,m \le 5 \times 10^4$。 ## 题解 首先二分答案，若此时二分的值为 $o$，则所有 $> o$ 的边都不能选。 每条边有选和不选两种状态，所以考虑 2-SAT。设第 $i$ 条边的状态为 $x_i$ 表示选择它，$x^{\prime}_i$ 表示不选。连边如下： 1. 对于一定不能选的边，连边 $x_i \to x^{\prime}_ i$。 2. 对于选出的边一定要是一个匹配，考虑一个点 $p$ 上的所有边 $x_{1\dots k}$，连边 $x_i \to x^{\prime}_ j(i \ne j)$。 3. 对于剩下的边每种颜色也一定要是一个匹配，考虑一个点 $p$ 上颜色相同的所有边 $x_{1\dots k}$，连边 $x^{\prime}_ i \to x_j(i \ne j)$。 但这样做第 $2,3$ 类边的边数为 $\mathcal O(m^2)$，注意到 2-SAT 有一个经典的建图优化——前缀优化。 先考虑第 $2$ 类边，设 $x_{1\dots k}$ 的前缀点为 $s_{1\dots k}$，$x^{\prime}_ {1\dots k}$ 的后缀点为 $s^{\prime}_ {1\dots k}$。连边如下： 1. $x_i \to s_i$，$s^{\prime}_ i \to x^{\prime}_ i$。 2. $s_{i-1} \to s_i$，$s^{\prime}_ i \to s^{\prime}_ {i-1}$。 3. $s_{i-1} \to x^{\prime}_ i$，$x_i \to s^{\prime}_ {i-1}$。  容易发现和第 $2$ 类边是等效的。 而第 $3$ 类边，就把第 $2$ 类边的箭头全部反过来即可。 然后 tarjan 就好了。 总时间复杂度 $\mathcal O((n + m) \log w)$。 ## 代码 ```cpp const int N = 5e4 + 7, M = 10 * N; int n, m, tot, l, r; int dfn[M], low[M], num, stk[M], top, ins[M], scc[M], cnt; vi v[N], s, e[M], ans; struct P { int u, v, c, t; inline void in() { rd(u), rd(v), rd(c), rd(t), r = max(r, t); } } p[N]; inline void work1() { int S, T; for (ui i = 0; i < s.size(); i++) { int x = ::s[i], y = ::s[i] + m, s = ++tot, t = ++tot; e[x].pb(s), e[t].pb(y); if (i) e[S].pb(s), e[t].pb(T), e[S].pb(y), e[x].pb(T); S = s, T = t; } s.clear(); } inline void work2() { int S, T; for (ui i = 0; i < s.size(); i++) { int x = ::s[i], y = ::s[i] + m, s = ++tot, t = ++tot; e[s].pb(x), e[y].pb(t); if (i) e[s].pb(S), e[T].pb(t), e[y].pb(S), e[T].pb(x); S = s, T = t; } s.clear(); } void tarjan(int x) { dfn[x] = low[x] = ++num, stk[++top] = x, ins[x] = 1; for (auto y : e[x]) if (!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]); else if (ins[y]) low[x] = min(low[x], dfn[y]); if (dfn[x] == low[x]) { ins[x] = 0, scc[x] = ++cnt; while (x != stk[top--]) { int y = stk[top+1]; ins[y] = 0, scc[y] = cnt; } } } inline void init(int o) { for (int i = 1; i <= m; i++) if (p[i].t > o) e[i].pop_back(); } inline bool pd(int o) { for (int i = 1; i <= m; i++) if (p[i].t > o) e[i].pb(i + m); for (int i = 1; i <= tot; i++) dfn[i] = 0; cnt = num = 0; for (int i = 1; i <= tot; i++) if (!dfn[i]) tarjan(i); for (int i = 1; i <= m; i++) if (scc[i] == scc[i+m]) return init(o), 0; return init(o), 1; } int main() { rd(n), rd(m), tot = m << 1; for (int i = 1; i <= m; i++) p[i].in(), v[p[i].u].pb(i), v[p[i].v].pb(i); for (int i = 1; i <= n; i++) { sort(v[i].begin(), v[i].end(), [&](int i, int j) { return p[i].c < p[j].c; }); s = v[i], work1(); for (ui l = 0, r = 0; l < v[i].size(); l = ++r) { s.pb(v[i][l]); while (r + 1 < v[i].size() && p[v[i][r+1]].c == p[v[i][r]].c) s.pb(v[i][++r]); work2(); } } if (!pd(r)) return prints("No"), 0; prints("Yes"); while (l < r) { int mid = (l + r) >> 1; if (pd(mid)) r = mid; else l = mid + 1; } pd(l); for (int i = 1; i <= m; i++) if (scc[i] < scc[i+m]) ans.pb(i); print(l, ' '), print(ans.size()); for (auto x : ans) print(x, ' '); return 0; } ```