ECR102 1473F Strange Set

問題

問題リンク：https://codeforces.com/contest/1473/problem/F

次を満たす集合 を'strange'とする。

• 

'strange'である集合 に対し の最大値を求めよ。

解法

いわゆる、「燃やす埋める問題」に落とし込めるので最小カットで解くことができる。

正負のペナルティは典型通り処理する。 のとき、iを選んでいるのにjを選んでいないことを禁止する辺を張る。

注意しないといけない点は、Dinic法の計算量は だが、愚直に辺を張ると辺の数が最大 程度になるためDinic法が になる。
辺の数を削減するため、辺を張るときは のうち最も大きい に辺を張る。そうすると辺の数が で抑えられる。

公式解説

Code

#include <bits/stdc++.h>
using namespace std;

template <typename T>
struct Dinic{
    // 行先、容量、逆辺の番号
    struct edge{
        int to, rev;
        T cap;
        edge() = default;
        edge(int to, T cap, int rev) : to(to), cap(cap), rev(rev) {}
    };
    std::vector<std::vector<edge> > G;
    std::vector<bool> used;
    std::vector<int> level, iter;

    Dinic() = default;
    Dinic(int n) : G(n), used(n), level(n), iter(n) {}
    
    T inf = std::numeric_limits<T>::max()/2;

    void init(int n){
        G.clear();
        G.resize(n);
        used.resize(n, false);
        level.resize(n);
        iter.resize(n);
    }

    void add_edge(int from, int to, T cap, bool directed = true){
        G[from].emplace_back(to, cap, int(G[to].size()));
        G[to].emplace_back(from, directed?0:cap, int(G[from].size())-1);
    }

    void bfs(int s){
        std::fill(level.begin(), level.end(), -1);
        std::queue<int> que;
        level[s] = 0;
        que.push(s);
        while(!que.empty()){
            int v = que.front();
            que.pop();
            for(edge &e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }

    // 増加路の探索
    T dfs(int v, int t, T f){
        if(v == t) return f;
        for(int &i = iter[v]; i<G[v].size(); i++){
            edge &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                T d = dfs(e.to, t, std::min(f, e.cap));
                if(d > 0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    T max_flow(int s, int t, T lim){
        T flow = 0;
        while(1){
            bfs(s);
            if(level[t] < 0) break;
            std::fill(iter.begin(), iter.end(), 0);
            T f;
            while((f = dfs(s, t, lim)) > 0){
                flow += f;
                lim -= f;
            }
        }
        return flow;
    }
    T max_flow(int s, int t){return max_flow(s, t, inf);}
};

bool solve(){
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for(int i=0;i<n;i++){
        scanf("%d", &a[i]);
    }
    Dinic<int> g(n+2);
    int S = n, T = n+1;  // in, out
    int ans = 0;
    for(int i=0;i<n;i++){
        int b;
        scanf("%d", &b);
        if(b < 0){
            g.add_edge(i,T,abs(b));
        }else{
            ans += b;
            g.add_edge(S,i,b);
        }
    }
    for(int i=0;i<n;i++){
        bool used[101]{};
        for(int j=i-1;j>=0;j--){
            if(a[i]%a[j]==0 && !used[a[j]]){
                g.add_edge(i,j,g.inf);
                used[a[j]] = true;
            }
        }
    }
    ans -= g.max_flow(S,T);
    printf("%d\n", ans);
    return false;
}

int main(){
    solve();
    return 0;
}

コメント

MLEしてから辺の数が多すぎることに気づいたので反省。フローの計算量をよく把握する。
辺を張るところで公式解説のコードのほうが賢い。