Editorial for Bedao Grand Contest 08 - RESTRICTIONS
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; const int N = 200005; int n, m, u, v, chk[N]; int cyc, dp[2 * N][2]; vector<int> stk, adj[N], bip[2 * N]; void DFS_1(int u) { chk[u] = 1; stk.push_back(u); for (int v : adj[u]) { if (chk[v] == 0) { DFS_1(v); } else if (chk[v] == 1) { cyc++; bip[v].push_back(cyc); bip[cyc].push_back(v); for (int i = stk.size() - 1; i >= 0; i--) { if (stk[i] == v) { break; } else { bip[stk[i]].push_back(cyc); bip[cyc].push_back(stk[i]); } } } } chk[u] = 2; stk.pop_back(); } void DFS_2(int u, int p = 0) { int mi = n; for (int v : bip[u]) { if (v != p) { DFS_2(v, u); if (u <= n) { // original node dp[u][0] += dp[v][1]; dp[u][1] += min(dp[v][0], dp[v][1]); } else { // cycle node dp[u][0] += min(dp[v][0], dp[v][1]); dp[u][1] += min(dp[v][0], dp[v][1]); mi = min(mi, max(0, dp[v][1] - dp[v][0])); } } } dp[u][1] += (u <= n ? 1 : mi); } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("RESTRICTIONS.inp", "r", stdin); // freopen("RESTRICTIONS.out", "w", stdout); cin >> n >> m; cyc = n; for (int i = 1; i <= m; i++) { cin >> u >> v; adj[u].push_back(v); } for (int i = 1; i <= n; i++) { if (chk[i] == 0) { DFS_1(i); } } int ans = 0; for (int i = n + 1; i <= cyc; i++) { if (dp[i][1] == 0) { DFS_2(i); ans += dp[i][1]; } } cout << n - ans; }
Comments