Chlience

【题解】LOJ 2509 「AHOI / HNOI2018」排列
Problem给定 $n$ 个整数 $a_i$ 以及 $n$ 个整数 $w_i$请组成一个长度为 $n$ 的 $a...
扫描右侧二维码阅读全文
07
2018/12

【题解】LOJ 2509 「AHOI / HNOI2018」排列

Problem

给定 $n$ 个整数 $a_i$ 以及 $n$ 个整数 $w_i$

请组成一个长度为 $n$ 的 $a$ 的排列 $a_{p[i]}$,并且使得若 $i < j$ 则 $a_{p[i]} \neq p[j]$

求 $\sum_{i=1}^niw_{p[i]}$ 的最大值

Solution

每个 $a_i$ 后方必然不能选择的点为 $a_{a_i}$
也就意味着 $a_{a_i}$ 必然需要排在 $a_i$ 前面

那么原问题就转化为如果有先后限制,如何使得 $\sum_{i=1}^niw_{p[i]}$ 最大

考虑变成一个拓扑序问题,对于每个点连一条 $a_i\rightarrow i$ 的边,表示要选第 $i$ 个必然要先选第 $a_i$ 个,这样形成了一棵以 $0$ 为根的树,消除了 $a$ 的限制,转为在满足拓扑序的前提下如何排列 $w$ 使其带权和最大

成环的情况就直接无解了

错误解法: 每次选择当前可选最小的

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL , int> p;
const int N = 500010;
LL read() {
    LL ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n;
int a[N] , fa[N] , in[N];
LL w[N];
struct edge {int t , n;}e[N];
int head[N] , tot;
struct heap {
    p node[N];
    int cnt;
    void push(p x) {
        int now = ++ cnt;
        node[now] = x;
        while(now / 2) {
            if(node[now] < node[now / 2]) {
                swap(node[now] , node[now / 2]);
                now /= 2;
            }
            else break;
        }
    }
    void pop() {
        node[1] = p{0 , 0};
        node[1] = node[cnt];
        node[cnt --] = p{0 , 0};
        int now = 1; 
        while(now * 2 <= tot) {
            int son = now * 2;
            if(son + 1 <= tot && node[son + 1] < node[son]) ++ son;
            if(node[now] > node[son]) {
                swap(node[now] , node[son]);
                now = son;
            }
            else break;
        }
    }
}h;
void addedge(int u , int v) {
    ++ tot;
    e[tot].t = v;
    e[tot].n = head[u];
    head[u] = tot;
}
void topology() {
    LL ans = 0;
    for(int i = 1 ; i <= n ; ++ i) {
        p x = h.node[1]; h.pop();
        ans += x.first * i;
        for(int j = head[x.second] ; j ; j = e[j].n)
            h.push(p{w[e[j].t] , e[j].t});
    }
    printf("%lld\n" , ans);
}
int main() {
    n = read();
    for(int i = 1 ; i <= n ; ++ i) a[i] = read();
    for(int i = 1 ; i <= n ; ++ i) w[i] = read();
    for(int i = 1 ; i <= n ; ++ i)
        if(!a[i]) h.push(p{w[i] , i});
        else addedge(a[i] , i);
    topology();
    return 0;
}

Hack数据:

hack.in
10 
6 6 10 1 7 0 0 1 7 7 
16 3 10 20 5 14 17 17 16 13 
hack.out
809

想想都知道不会这么简单嘛(估计也就我这种智障手写堆了...)

考虑一个目前最小的点,如果其父亲被选,必然会马上选择这个点,所以说可以将这当前点和其父亲节点关系确定下来,合为一个点

如何比较两个点(或者说两个集合)之间的大小呢?

若有一个大小为 $n$,元素和为 $X$ 的集合
一个大小为 $m$,元素和为 $Y$ 的集合

那么如果 $X$ 先选,则额外贡献为 $mY$
同理,如果 $Y$ 先选,则额外贡献为 $nX$

那么只需选 $\frac{sum}{n}$ 也就是 $\bar x$ 较小的

根据传递性原理,每次选 $\bar x$ 最小的即可保证总答案最小

最终使用并查集维护父子关系,用 $heap$ 来维护最小值
因为支持删除,所以还要写个删除堆

当然使用优先队列也是一样的

注意 $0$ 是不算入的!

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <long double , int> p;
const int N = 500010;
LL read() {
    LL ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
int n;
int a[N] , f[N];
int fa[N];
LL num[N] , sum[N];
LL ans;
struct heap {
    p node[N << 1];
    int cnt;
    void push(p x) {
        int now = ++ cnt;
        node[now] = x;
        while(now / 2) {
            if(node[now] < node[now / 2]) {
                swap(node[now] , node[now / 2]);
                now /= 2;
            }
            else break;
        }
    }
    void pop() {
        node[1] = p{0 , 0};
        node[1] = node[cnt];
        node[cnt --] = p{0 , 0};
        int now = 1; 
        while(now * 2 <= cnt) {
            int son = now * 2;
            if(son + 1 <= cnt && node[son + 1] < node[son]) ++ son;
            if(node[now] > node[son]) {
                swap(node[now] , node[son]);
                now = son;
            }
            else break;
        }
    }
    p top() {return node[1];}
    bool empty() {return cnt == 0;}
}h , d;
//priority_queue <p , vector<p> , greater<p>> h , d;
//记得重载优先队列
void ins(p x) {
    h.push(x);
    while(!d.empty() && d.top() == h.top()) {d.pop(); h.pop();}
}
void del(p x) {
    d.push(x);
    while(!d.empty() && d.top() == h.top()) {d.pop(); h.pop();}
}
p get() {
    p re = h.top(); h.pop();
    while(!d.empty() && d.top() == h.top()) {d.pop(); h.pop();}
    return re;
}
int find(int x) {return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);}
int main() {
    n = read();
    for(int i = 0 ; i <= n ; ++ i) fa[i] = i;
    for(int i = 1 ; i <= n ; ++ i) {
        f[i] = read();
        int x = find(i) , y = find(f[i]);
        if(x == y) {puts("-1"); return 0;}
        fa[x] = y;
    }
    for(int i = 0 ; i <= n ; ++ i) fa[i] = i;
    for(int i = 1 ; i <= n ; ++ i) {
        sum[i] = read(); num[i] = 1;
        ins(p{(long double)sum[i] , i});
        ans += sum[i];
    }
    for(int i = 1 ; i <= n ; ++ i) {
        int x = get().second , y = find(f[x]);
        if(y) del(p{(long double)sum[y] / (long double)num[y] , y});
        ans += sum[x] * num[y];
        sum[y] += sum[x]; num[y] += num[x];
        fa[x] = y;
        if(y) ins(p{(long double)sum[y] / (long double)num[y] , y});
    }
    printf("%lld\n" , ans);
    return 0;
}
Last modification:February 11th, 2019 at 08:36 am

Leave a Comment