めっちゃ面白い問題！

問題概要

$N$ 個の直方体がある。 $i$ 番目の直方体は $1 \times A_{i} \times B_{i}$ の形をしている。

今、これらの直方体からいくつかを選んで積み木を作る。このとき、奥行き方法は必ず長さが $1$ になるようにする。

縦または横方向については、 $A_{i} \times B_{i}$ としてもよいし、 $B_{i} \times A_{i}$ としてもよい。

ただし、積み木の横の長さは必ず狭義単調減少になるようにする必要がある。

作れる積み木の高さの最大値を求めよ。

制約

$1 \le N \le 1000$
$1 \le A_{i}, B_{i} \le 10^{6}$

考えたこと

入力例 1 を見てみる。

これは、

最下段に、横 40、高さ 10
二段目に、横 20、高さ 30
最上段に、横 10、高さ 40

とする場合が最適で、高さは 80 となる。

各直方体について、向きが 2 通りずつ考えられて、さらにそれらをどの順序で積むかにも任意性があって難しい。しかしながら、各直方体ごとに向きが 2 通りずつあるという設定は「割当問題」が想起される。

単調減少制約を言い換えて、割当問題に

さらに、積み木の横の長さが狭義単調減少という条件は、実は難しくない。要するに

「積み木を構成するどの直方体も、並べたときの横の長さが互いに相異なるようにせよ」

ということなのだ。この条件さえ満たせば、単に横の長さが長いものから積んでいけばいいだけなのだ。

というわけで、

左側ノード： $N$ 個の直方体
右側ノード：直方体の横の長さとして考えられる値たち (高々 $O(N)$ 通り)

というふうにした割当問題とみなせる。

さらに詰める

割当問題に帰着できそうだとわかった。さらに、各 $i$ 番目の直方体に対して、

長さ $A_{i}$ を表す右側ノードと、コスト $B_{i}$ の辺
長さ $B_{i}$ を表す左側ノードと、コスト $A_{i}$ の辺

を結べばよい。こうしてできたグラフ上で、最大重みのマッチングを求めれば良い。ただし、マッチング辺の本数は任意とする。

これは、最小費用流で解ける。マッチング辺の本数が任意という部分については、ソースからシンクへ容量 INF、コスト 0 の辺を貼っておけば良い。そして、流量 $N$ の最小費用流を流せば良い。

提出コード

#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using pll = pair<long long, long long>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define REP(i, n) for (long long i = 0; i < (long long)(n); ++i)
#define REP2(i, a, b) for (long long i = a; i < (long long)(b); ++i)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, deque<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }


// edge class (for network-flow)
template<class FLOWTYPE, class COSTTYPE> struct Edge {
    int rev, from, to, id;
    FLOWTYPE cap, icap;
    COSTTYPE cost;
    Edge(int r, int f, int t, FLOWTYPE ca, COSTTYPE co, int id = -1) :
        rev(r), from(f), to(t), cap(ca), icap(ca), cost(co), id(id) {}
    friend ostream& operator << (ostream& s, const Edge& E) {
        if (E.cap > 0)
            return s << E.from << "->" << E.to <<
                '(' << E.cap << ',' << E.cost << ')';
        else return s;
    }
};

// graph class (for network-flow)
template<class FLOWTYPE, class COSTTYPE> struct Graph {
    vector<vector<Edge<FLOWTYPE, COSTTYPE> > > list;
    
    Graph(int n = 0) : list(n) { }
    void init(int n = 0) { list.clear(); list.resize(n); }
    void reset() { for (int i = 0; i < (int)list.size(); ++i) for (int j = 0; j < list[i].size(); ++j) list[i][j].cap = list[i][j].icap; }
    inline vector<Edge<FLOWTYPE, COSTTYPE> >& operator [] (int i) { return list[i]; }
    inline const size_t size() const { return list.size(); }
    
    inline Edge<FLOWTYPE, COSTTYPE> &redge(const Edge<FLOWTYPE, COSTTYPE> &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    
    void addedge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) {
        list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id));
        list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, 0, -cost));
    }
    
    void add_undirected_edge(int from, int to, FLOWTYPE cap, COSTTYPE cost, int id = -1) {
        list[from].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[to].size(), from, to, cap, cost, id));
        list[to].push_back(Edge<FLOWTYPE, COSTTYPE>((int)list[from].size() - 1, to, from, cap, cost, id));
    }

    friend ostream& operator << (ostream& s, const Graph& G) {
        s << endl;
        for (int i = 0; i < G.size(); ++i) {
            s << i << ":";
            for (auto e : G.list[i]) s << " " << e;
            s << endl;
        }
        return s;
    }
};

// min-cost flow (by primal-dual)
template<class FLOWTYPE, class COSTTYPE> COSTTYPE MinCostFlow(Graph<FLOWTYPE, COSTTYPE> &G, int s, int t, FLOWTYPE f) {
    int n = (int)G.size();
    vector<COSTTYPE> dist(n, -1);
    vector<int> prevv(n), preve(n), seen(n, 0);
    COSTTYPE res = 0;
    while (f > 0) {
        seen.assign(n, 0);
        dist[s] = 0;
        seen[s] = true;
        while (true) {
            bool update = false;
            for (int v = 0; v < n; ++v) {
                if (!seen[v]) continue;
                for (int i = 0; i < G[v].size(); ++i) {
                    Edge<FLOWTYPE, COSTTYPE> &e = G[v][i];
                    if (e.cap > 0 && (!seen[e.to] || dist[e.to] > dist[v] + e.cost)) {
                        dist[e.to] = dist[v] + e.cost;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        seen[e.to] = true;
                        update = true;
                    }
                }
            }
            if (!update) break;
        }
        if (!seen[t]) return -1;
        FLOWTYPE d = f;
        for (int v = t; v != s; v = prevv[v]) {
            d = min(d, G[prevv[v]][preve[v]].cap);
        }
        f -= d;
        res += dist[t] * d;
        for (int v = t; v != s; v = prevv[v]) {
            Edge<FLOWTYPE, COSTTYPE> &e = G[prevv[v]][preve[v]];
            Edge<FLOWTYPE, COSTTYPE> &re = G.redge(e);
            e.cap -= d;
            re.cap += d;
        }
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N), lens;
    for (int i = 0; i < N; ++i) {
        cin >> A[i] >> B[i];
        lens.push_back(A[i]);
        lens.push_back(B[i]);
    }
    sort(lens.begin(), lens.end());
    lens.erase(unique(lens.begin(), lens.end()), lens.end());
    
    // グラフ
    int source = N + lens.size(), sink = N + lens.size() + 1;
    Graph<int,int> G(N + lens.size() + 2);
    
    // ソース → 直方体
    for (int i = 0; i < N; ++i) {
        G.addedge(source, i, 1, 0);
    }
    // 長さ → シンク
    for (int i = 0; i < lens.size(); ++i) {
        G.addedge(i+N, sink, 1, 0);
    }
    // ソース → シンク
    G.addedge(source, sink, N, 0);
    // 直方体 → シンク
    for (int i = 0; i < N; ++i) {
        int aid = lower_bound(lens.begin(), lens.end(), A[i]) - lens.begin();
        int bid = lower_bound(lens.begin(), lens.end(), B[i]) - lens.begin();
        G.addedge(i, aid+N, 1, -B[i]);
        G.addedge(i, bid+N, 1, -A[i]);
    }
 
    int res = -MinCostFlow(G, source, sink, N);
    cout << res << endl;
}