loj#2509. 「AHOI / HNOI2018」排列(思维题 set)
程序员文章站
2022-04-28 11:10:42
题意 "题目链接" Sol 神仙题Orz 首先不难看出如果我们从$a_i$向$i$连一条边,我们会得到以$0$为根的树(因为每个点一定都有一个入度,出现环说明无解),同时在进行排列的时候需要保证父亲节点一定在孩子节点之前出现 接下来考虑直接贪心。对于某些权值很小的点,我们需要让其尽早出现,同时又要满 ......
题意
sol
神仙题orz
首先不难看出如果我们从\(a_i\)向\(i\)连一条边,我们会得到以\(0\)为根的树(因为每个点一定都有一个入度,出现环说明无解),同时在进行排列的时候需要保证父亲节点一定在孩子节点之前出现
接下来考虑直接贪心。对于某些权值很小的点,我们需要让其尽早出现,同时又要满足选择的条件。
那么我们可以从小的点开始,依次向他的父亲合并,并删除该点(也就是如果父亲一但被删除,那么这个点立马被删除)
下面的内容抄袭摘抄自
然后直接用set搞一搞
复杂度:\(o(n\log n)\)
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 5e5 + 10, ss = 1e7 + 10; template<typename a, typename b> inline void chmax(a &x, b y) { x = x > y ? x : y; } inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, a[maxn], fa[maxn], vis[maxn], ufa[maxn]; ll w[maxn], siz[maxn]; vector<int> v[maxn]; struct comp { bool operator ()(int x, int y) { return w[x] * siz[y] == w[y] * siz[x] ? x < y : w[x] * siz[y] < w[y] * siz[x]; } }; int find(int x) { return ufa[x] == x ? ufa[x] : ufa[x] = find(ufa[x]); } set<int, comp> s; int dfs(int x) { vis[x] = 1; for(auto &to : v[x]) { if(vis[to] == 1) return 1; if(dfs(to)) return 1; } vis[x] = 2; return 0; } int main() { n = read(); for(int i = 1; i <= n; i++) { fa[i] = read(); v[fa[i]].push_back(i); } for(int i = 1; i <= n; i++) if(!vis[i]) if(dfs(i)) {puts("-1"); return 0;} for(int i = 1; i <= n; i++) w[i] = read(), ufa[i] = i, siz[i] = 1, s.insert(i); siz[0] = 1; ufa[0] = 0; ll ans = 0; for(int i = 1; i <= n; i++) { int x = *s.begin(); s.erase(s.begin()); int f = find(fa[find(x)]); if(f) s.erase(f); ans += siz[f] * w[x]; siz[f] += siz[x]; w[f] += w[x]; ufa[x] = f; if(f) s.insert(f); } cout << ans; return 0; } /* 3 0 1 1 5 7 3 */
上一篇: 花了几百万换来的用人道理
下一篇: http状态码