Editorial for VOI 15 Bài 3 - Kế hoạch cải tổ
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.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #include <climits> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++) #define RESET(a, v) memset((a), (v), sizeof((a))) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int N = 100005; using namespace std; vector<II> e; VI a[N]; int low[N], num[N], cnt[N], par[N], sz[N]; bool isBridge[N]; int n, m, timer, cntBridge, cc; void dfs(int u) { num[u] = ++timer; low[u] = INT_MAX; cnt[cc]++; sz[u] = 1; TR(v, a[u]) if (*v != par[u]) { if (num[*v]) low[u] = min(low[u], num[*v]); else { par[*v] = u; dfs(*v); low[u] = min(low[u], low[*v]); sz[u] += sz[*v]; } } if (low[u] >= num[u] && par[u]) cntBridge += isBridge[u] = 1; } LL solve() { if (cc > 2) return 0; if (cc == 2) return (LL)cnt[1] * cnt[2] * (m - cntBridge); LL ans = 0, maxE = (LL)n * (n - 1) / 2; TR(it, e) { int u = it -> X; int v = it -> Y; if (num[u] > num[v]) swap(u, v); if (par[v] == u && isBridge[v]) ans += (LL)sz[v] * (sz[1] - sz[v]) - 1; else ans += maxE - m; } return ans; } int main() { ios :: sync_with_stdio(0); cin.tie(0); cin >> n >> m; int u, v; FOR(i, 0, m) { cin >> u >> v; a[u].PB(v); a[v].PB(u); e.PB(MP(u, v)); } REP(i, 1, n) if (num[i] == 0) { cc++; dfs(i); } cout << solve(); return 0; }
Comments
include <bits/stdc++.h>
define th1 first
define th2 second
define int long long
define _(k) ((k) & (-(k)))
using namespace std;
const int N = 5 + 2e5; const int INF = 0x3f3f3f3f; int n, m, num[N], low[N], vis[N], hint[N], pa[N], cnt = 0, cau = 0, khop = 0, sz[N], kq = 0; int amount = 0, node = 0; vector<int> g[N];
struct T { int u, v; } e[N];
void dfs(int u) { num[u] = low[u] = ++cnt; sz[u] = 1; for (int id : g[u]) { if (vis[id]) continue; vis[id] = 1; int v = e[id].u + e[id].v - u; if (!num[v]) { pa[v] = u; dfs(v); sz[u] += sz[v]; low[u] = min(low[u], low[v]); if (low[v] > num[u]) { cau++; kq += (sz[v] * (n - sz[v]) - 1); } } else low[u] = min(low[u], num[v]); } }
void solve() { if (amount >= 3) cout << 0 << '\n'; else if (amount == 2) { cout << (m - cau) * node * (n - node) << '\n'; } else { kq += ((m - cau) * (n * (n - 1) / 2 - m)); cout << kq; } }
int32t main() { iosbase::syncwithstdio(0); cin.tie(0); #define TASKNAME "a" if (fopen(TASKNAME".inp", "r")) { freopen(TASKNAME".inp", "r", stdin); freopen(TASKNAME".out", "w", stdout); } cin >> n >> m; for (int i = 1; i <= m; i++) { cin >> e[i].u >> e[i].v; g[e[i].u].pushback(i); g[e[i].v].pushback(i); }
}