Submission #1225219

#TimeUsernameProblemLanguageResultExecution timeMemory
1225219Bui_Quoc_Cuong통행료 (APIO13_toll)C++20
0 / 100
5 ms9792 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAX = 3e5 + 5; int n, m, k; struct Edges{ int u, v, w; } MST[MAX], SE[MAX], E[MAX]; int c[MAX]; vector <int> g[MAX]; int weight[MAX], par[MAX], h[MAX]; int sz[MAX]; int lab[MAX]; vector <array <int, 3>> edges; bool in_MST[MAX]; int find(int x){ return lab[x] < 0 ? x : lab[x] = find(lab[x]); } bool joint(int u, int v){ int x = find(u), y = find(v); if(x == y) return false; if(lab[x] > lab[y]) swap(x, y); lab[x]+= lab[y]; lab[y] = x; return true; } void reset_dsu(){ memset(lab, - 1, sizeof lab); } void dfs(int u, int p){ sz[u] = c[u]; for(int v : g[u]) if(v != p){ par[v] = u; h[v] = h[u] + 1; dfs(v, u); sz[u]+= sz[v]; } } void update_edge(int u, int v, int w){ if(h[u] < h[v]) swap(u, v); while(h[u] > h[v]){ weight[u] = min(weight[u], w); u = par[u]; } while(u != v){ weight[u] = min(weight[u], w); weight[v] = min(weight[v], w); u = par[u], v = par[v]; } } namespace sub123{ void solve(){ ll ans = 0; reset_dsu(); for(int mask = 0; mask < (1 << k); mask++){ bool ok = 1; for(int i = 1; i <= n; i++) g[i].clear(), lab[i] = - 1, weight[i] = 2e9, in_MST[i] = 0; for(int i = 0; i < k; i++) if((mask >> i) & 1){ if(!joint(SE[i + 1].u, SE[i + 1].v)){ ok = false; break; } if((mask >> i) & 1){ g[SE[i + 1].u].push_back(SE[i + 1].v); g[SE[i + 1].v].push_back(SE[i + 1].u); } } if(!ok) continue; for(int i = 1; i <= n - 1; i++){ if(joint(MST[i].u, MST[i].v)){ in_MST[i] = 1; g[MST[i].u].push_back(MST[i].v); g[MST[i].v].push_back(MST[i].u); } } dfs(1, - 1); for(int i = 1; i <= n; i++) if(!in_MST[i]){ update_edge(MST[i].u, MST[i].v, MST[i].w); } ll sum = 0; for(int i = 0; i < k; i++) if((mask >> i) & 1){ int u = SE[i + 1].u, v = SE[i + 1].v; if(h[u] > h[v]) swap(u, v); sum+= 1LL * weight[v] * sz[v]; } ans = max(ans, sum); } cout << ans; } } namespace sub45{ int color[MAX], cnt; void dfs(int u, int col){ color[u] = col; for(int v : g[u]) if(color[v] == - 1){ dfs(v, col); } } ll sum_c[MAX]; ll SUM[MAX]; void DFS(int u, int p){ SUM[u] = sum_c[u]; for(int v : g[u]) if(v != p){ DFS(v, u); SUM[u]+= SUM[v]; } } void solve(){ reset_dsu(); for(int i = 1; i <= k; i++){ joint(SE[i].u, SE[i].v); } sort(E + 1, E + 1 + m, [&](Edges u, Edges v){ return u.w < v.w; }); for(int i = 1; i <= m; i++) if(joint(E[i].u, E[i].v)){ g[E[i].u].push_back(E[i].v); g[E[i].v].push_back(E[i].u); in_MST[i] = 1; } reset_dsu(); vector <Edges> extra; for(int i = 1; i <= m; i++) if(in_MST[i]){ joint(E[i].u, E[i].v); } for(int i = 1; i <= m; i++) if(!in_MST[i]){ if(joint(E[i].u, E[i].v)){ extra.push_back(E[i]); } } memset(color, - 1, sizeof color); for(int i = 1; i <= n; i++) if(color[i] == - 1){ cnt++; dfs(i, cnt); } for(int i = 1; i <= k; i++) SE[i].u = color[SE[i].u], SE[i].v = color[SE[i].v]; for(auto &x : extra) x.u = color[x.u], x.v = color[x.v]; for(int i = 1; i <= n; i++) sum_c[color[i]]+= c[i]; ll ans = 0; for(int mask = 0; mask < (1 << k); mask++){ for(int i = 1; i <= cnt; i++) g[i].clear(), lab[i] = - 1, weight[i] = 2e9; bool ok = 1; for(int i = 0; i < k; i++) if((mask >> i) & 1){ if(!joint(SE[i + 1].u, SE[i + 1].v)){ ok = 1; break; } if((mask >> i) & 1){ g[SE[i + 1].u].push_back(SE[i + 1].v); g[SE[i + 1].v].push_back(SE[i + 1].u); } } if(!ok) continue; for(auto x : extra){ if(joint(x.u, x.v)){ g[x.u].push_back(x.v); g[x.v].push_back(x.u); } } DFS(1, - 1); for(auto x : extra){ update_edge(x.u, x.v, x.w); } ll sum = 0; for(int i = 0; i < k; i++) if((mask >> i) & 1){ int u = SE[i + 1].u, v = SE[i + 1].v; if(h[u] > h[v]) swap(u, v); sum+= 1LL * weight[v] * SUM[v]; } ans = max(ans, sum); } cout << ans; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); // freopen("kieuoanh.inp", "r", stdin); // freopen("kieuoanh.out", "w", stdout); cin >> n >> m >> k; for(int i = 1; i <= m; i++){ int u, v, w; cin >> u >> v >> w; edges.push_back({w, u, v}); E[i] = {u, v, w}; } for(int i = 1; i <= k; i++) cin >> SE[i].u >> SE[i].v; for(int i = 1; i <= n; i++) cin >> c[i]; reset_dsu(); sort(edges.begin(), edges.end()); int cnt = 0; for(array <int, 3> it : edges){ int u = it[1], v = it[2], w = it[0]; if(joint(u, v)){ MST[++ cnt] = {u, v, w}; } } /// thay vì ta duyệt lại từng cạnh để check thì có nhận xét /* ta nén cây lại xét k cạnh đặc biệt MST 1 gôm : k cạnh đặc biệt + cạnh mặc định MST 2 gồm : cạnh mặc định từ đó ta có những cạnh có khả năng cạnh tranh biến đồ thị về các thành phần liên thông giờ ta chỉ cần duyệt mask để tìm cạnh kết nối chúng lại ta không cần kết nối một số cạnh kh cần thiết vì khi đã xét đủ k cạnh thì ta đã có những cạnh có sẵn trong mst */ return sub45::solve(), 0; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...