ARC085 E - MUL

E - MUL

問題概要

整数a1,a2,..,aNが与えられる。
ある自然数kを選び、N以下の全てのkの倍数ik(i>=1)についてa_ik = 0にするという操作が可能な時、
a1,a2,...,aNの総和の最大値を求めよ。
1<=N<=100, |ai| <= 10⁹

解法

MinCutする。
1〜Nの整数をノードとし、S,T2つのノードを加える。
ここで辺をカットしていき、S側にあるものを0にし、T側にあるものを0にしないと決める。
Mincutは最小カットなので、最大値を求めるためにMincutを理想の状態からの最小ペナルティと考える。
理想の状態は正の数だけ取ることだから、ai >= 0なるaiの和を先に求めておく。
ai>=0なるiに対してはT側にあるのが理想であり、逆にS側にあるとaiのペナルティがあるからiからTに対してai(>=0)の辺を張る。
ai<0なるiに対してはS側にあるのが理想であり、T側にあると-aiのペナルティがあるからSからiに対してai(>0)の辺を張る。
またi,j(jはiの倍数)に対して、iがS側、jがT側にあると矛盾するからiからjに対してINFの辺を張る。
逆にiがT側、jがS側の時は矛盾しないのでjからiには辺を張らなくて良い。
以下の条件でグラフを形成しSからTへのMaxFlow = MinCutを求め、理想の状態から引く。

メモ

典型問題らしいが、やるのは初めてだった。
よく見ると蟻本にも書いてあった。
使い方については解説放送と、
診断人さんの神スライドで勉強した。
解答でのiからjに辺を張ってjからiに張らないのがわからなかったのだが、スライドの29ページで理解した。
i -> j のみに辺を張ることでiがS側、jがT側にある時にはMinCutが成立しないようになる。
毎回図を書かないと理解できなさそう。
MaxFlowの実装についてはtubo28さんのDinic法の実装を参考にした。
そのうち自分で実装したい(いつになるんだ)

コード

#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<utility>
#include<memory>
#include<cmath>
#include<stack>
#include<tuple>
#include<numeric>
#include<cassert>

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 102;
const ll lmod = 1e9+7;

using Flow = ll;

struct Edge {
  int to, from;
  Flow cap;
  Edge(int from, int to, Flow f) : from(from), to(to), cap(f) {}
};

using Graph = vector<vector<Edge>>;

struct Dinic {
    int n, s, t;
    std::vector<int> level, prog, que;
    std::vector<std::vector<Flow>> cap, flow;
    std::vector<std::vector<int>> g;
    Flow inf;
    Dinic(const Graph &graph)
        : n(graph.size()),
          cap(n, std::vector<Flow>(n)),
          flow(n, std::vector<Flow>(n)),
          g(n, std::vector<int>()),
          inf(std::numeric_limits<Flow>::max() / 8) {
        for (int i = 0; i < n; i++) {
            for (auto &e : graph[i]) {
                int u = e.from, v = e.to;
                Flow c = e.cap;
                cap[u][v] += c;
                cap[v][u] += c;
                flow[v][u] += c;
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
    }
    inline Flow residue(int u, int v) { return cap[u][v] - flow[u][v]; }
    Flow solve(int s_, int t_) {
        this->t = t_, this->s = s_;
        que.resize(n + 1);
        Flow res = 0;
        while (levelize()) {
            prog.assign(n, 0);
            res += augment(s, inf);
        }
        return res;
    }
    bool levelize() {
        int l = 0, r = 0;
        level.assign(n, -1);
        level[s] = 0;
        que[r++] = s;
        while (l != r) {
            int v = que[l++];
            if (v == t) break;
            for (const int &d : g[v])
                if (level[d] == -1 && residue(v, d) != 0) {
                    level[d] = level[v] + 1;
                    que[r++] = d;
                }
        }
        return level[t] != -1;
    }
    Flow augment(int v, Flow lim) {
        Flow res = 0;
        if (v == t) return lim;
        for (int &i = prog[v]; i < (int)g[v].size(); i++) {
            const int &d = g[v][i];
            if (residue(v, d) == 0 || level[v] >= level[d]) continue;
            const Flow aug = augment(d, std::min(lim, residue(v, d)));
            flow[v][d] += aug;
            flow[d][v] -= aug;
            res += aug;
            lim -= aug;
            if (lim == 0) break;
        }
        return res;
    }
};

int main(){
  int N; cin >> N ;
  Graph g(N+2);
  ll a[MAX_N];
  ll _sum = 0;
  rep(i,N){
    scanf("%lld",a+i);
    if(a[i]>0) _sum += a[i];
  }
  const int S = N,T = N+1;
  rep(i,N){
    if(a[i]<0){
      g[S].pb(Edge(S,i,-a[i]));

    }else{
      g[i].pb(Edge(i,T,a[i]));
    }
  }
  rep(i,N){
    int num1 = i+1;
    for(int num2 = num1*2; num2 <= N; num2 += num1){
      g[num1-1].pb(Edge(num1-1,num2-1,LINF));
    }
  }
  Dinic dn(g);
  cout << _sum - dn.solve(S,T) << endl;
  return 0;
}