AOJ 2726 Black Company - すいバカ日誌

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2726

問題概要

N 人の従業員がいて，それぞれ成果を c(i) あげたとする．成果に応じて，報酬 p(i) を分配する．
ただし，それぞれの従業員には親しい人が何人か存在する．
従業員 i が j と親しいときは，以下を満たすように p(i)，p(j) を定める．

c(i) < c(j) ならば p(i) < p(j)
c(i) > c(j) ならば p(i) > p(j)
c(i) == c(j) ならば p(i) == p(j)

また，i と j が親しく，かつ i と k が親しいときは，j と k に対しても上と同じ条件を満たす必要がある．（ただしこの時は，j と k は親しいとは言わない．ただ条件を満たす必要があるだけ．もちろん j と k がもともと親しい場合もある．）
このような条件をみたすように，従業員に払う給料の総額を最小化せよ．

1 <= N <= 10^5
0 <= M <= 2 * 10^5
1 <= c(i) <= 10^5

解法

この手の，「a は b よりある順序関係のもとで"小さい"」を表現するのは，a -> b と辺を張るのがよくあるやり方だが，この問題もそのようにやる．
直接親しい場合は入力を受け取ったときに辺を張ればよい．
間接的に条件を満たす必要がある人は，ある人 i を定めたときに，隣接している人をすべて列挙して，成果順にソートし（ソートした後の人の集合を adj(i) で表す），adj(i)(j) -> adj(i)(j+1) と辺を張ればよい．
あとはこのグラフ上で，最も成果が小さい人から順に，給料を 1, 2, ... と定めていくだけ．これは配るDPのイメージでできる．

さて，問題になるのは，同じ成果を上げた人が存在し，かつ条件を満たす必要がある場合だが，この場合は，辺を張る代わりに，その頂点を縮約してしまえばよい．
縮約には union-find 木を使うと楽で，縮約前のサイズ分 dp で求めた値に掛けて加えてやればOK．

計算量はソートが一番大きくて，O(NlogN + VlogV)．(それと定数倍)

ソースコード

#include <bits/stdc++.h>
using namespace std;
 
using P = pair<int, int>;
using ll = long long;
 
class union_find {
public:
    union_find(int n)
        : par_(n, -1)
    {}
    void init(int n) {
        par_.assign(n, -1);
    }
 
    int root(int x) {
        return par_[x] < 0 ? x : par_[x] = root(par_[x]);
    }
 
    bool unite(int x, int y) {
        x = root(x); y = root(y);
        if(x == y) {
            return false;
        } else {
            if(par_[x] < par_[y]) {
                par_[x] += par_[y];
                par_[y] = x;
            } else {
                par_[y] += par_[x];
                par_[x] = y;
            }
            return true;
        }
    }
 
    bool same(int x, int y) {
        return root(x) == root(y);
    }
 
    int size(int x) {
        return -par_[root(x)];
    }
 
private:
    std::vector<int> par_;
};
 
int main() {
    int N;
    cin >> N;
    vector<int> c(N);
    for(int i=0; i<N; ++i) {
        cin >> c[i];
    }
    int M;
    cin >> M;
    union_find uf(N);
    vector<vector<int>> g(N);
    vector<vector<P>> next(N);
    for(int i=0; i<M; ++i) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(c[a] > c[b]) {
            g[b].push_back(a);
        } else if(c[a] < c[b]) {
            g[a].push_back(b);
        } else {
            uf.unite(a, b);
        }
        next[a].emplace_back(c[b], b);
        next[b].emplace_back(c[a], a);
    }
 
    for(int i=0; i<N; ++i) {
        if(next[i].size() == 0) {
            continue;
        }
        sort(next[i].begin(), next[i].end());
        for(int j=0; j<next[i].size()-1; ++j) {
            P u = next[i][j], v = next[i][j+1];
            if(u.first == v.first) {
                uf.unite(u.second, v.second);
            } else {
                g[u.second].push_back(v.second);
            }
        }
    }
 
    vector<int> order;
    vector<ll> dp(N);
    for(int i=0; i<N; ++i) {
        if(uf.root(i) == i) {
            order.push_back(i);
            dp[i] = 1;
        } else {
            for(auto& v : g[i]) {
                g[uf.root(i)].push_back(v);
                g[i].clear();
            }
        }
    }
    sort(order.begin(), order.end(), [&](int const v1, int const v2) {
        return c[v1] < c[v2];
    });
    ll res = 0;
    for(auto i : order) {
        for(auto to : g[i]) {
            dp[uf.root(to)] = max(dp[uf.root(to)], dp[i] + 1);
        }
        res += dp[i] * uf.size(i);
    }
    cout << res << endl;
}