E - MUL AtCoder Regular Contest 085

E: MUL - AtCoder Regular Contest 085 | AtCoder

問題文

宝石が N 個あり，それぞれ 1,2,…,N と数が書かれています。

あなたは，以下の操作を好きなだけ行うことが出来ます(一度も行わなくてもよいです)。

• 正整数 x を選ぶ。x の倍数が書かれた宝石を全て叩き割る。

そして，i が書かれていた宝石が割られずに残っていた場合，a_i 円貰います。 ただし，この a_i は負の場合もあり，その場合はお金を払わなくてはいけません。

うまく操作を行った時，あなたは最大で何円お金を貰えるでしょうか？

制約

• 入力は全て整数
• 1≤N≤100
• |a_i|≤10⁹

解法

最小カットを使って「燃やす埋める問題」を解く（参考）

燃やす埋める問題というらしい。

基本的に頂点をs側かt側に割り振る事で最大の利益を求めるが、今回は利益がマイナスのものがあるので、考えうる最大の利益との損失をコストにすることで、+にする。

aiを砕いた場合、その倍数ajも砕かないことはaiを砕く時、ajが砕かれていないときに無限の損失を貼る事で実現できる。

具体的にはs側が「砕かない」の時、iからjへ無限の辺を貼る。（上のスライドのp29あたり参照）

こうすることでaiを割ったがajを割らないという状況をなくせる。

なぜなら、s側のaiかt側のajが0になるため、最小カットがt側のai（aiを砕く）とs側のaj(ajを砕かない)となることがありえないから。

ちなみに、s側が割るで、t側が割らないのときはiからjではなく、jからiに辺を貼る必要がある

こうした。0の辺はいらないけど、あった方が安心を得られると言われている。

@SuppressWarnings("unchecked")
public class Main
{
    static FastScanner sc = new FastScanner(System.in);
    static int INF = 1234567890;
    static long LINF = 123456789123456789L;
    static int N;

    public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        edges = Stream.generate(ArrayList::new).limit(N + 2).toArray(ArrayList[]::new);
        int s = 0;
        int t = N + 1;
        long max = 0;
        //考えうる最高の利益からの損失をコストとする
        //s側が割らない
        for (int i = 1; i < N + 1; i++)
        {
            int v = sc.nextInt();
            if (v > 0)
            {
                max += v;
                //aiを割らなかった時の損失
                addEdge(s, i, 0);//意味ない　気持ち
                //aiを割った時の損失
                addEdge(i, t, v);
            }
            else
            {
                addEdge(s, i, -v);
                addEdge(i, t, 0);//気持ち　いらん
            }
        }
        for (int i = 1; i < N + 1; i++)
        {
            for (int j = 2; j * i <= N; j++)
            {
                //aiを割って、a i*jを割らないという状況を避ける
                addEdge(i, i * j, INF);
            }
        }
        //最小の損失を求め、ひく。
        System.out.println(max - dinic(s, t));
    }

    static List<Edge>[] edges;
    static int[] level, iter;

    public static boolean bfs(int s, int t)
    {
        Arrays.fill(level, -1);
        level[s] = 0;
        ArrayDeque<Integer> que = new ArrayDeque<>();
        que.push(s);
        while (!que.isEmpty())
        {
            int v = que.poll();
            for (Edge e : edges[v])
            {
                if (level[e.to] < 0 && e.cap > 0)
                {
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
        return level[t] != -1;
    }

    public static long dfs(int v, int t, long f)
    {
        if (v == t)
        {
            return f;
        }
        for (int i = iter[v]; i < edges[v].size(); i++, iter[v]++)
        {
            Edge e = edges[v].get(i);
            if (e.cap > 0 && level[v] < level[e.to])
            {
                long flow = dfs(e.to, t, Math.min(f, e.cap));
                if (flow == 0) continue;
                e.cap -= flow;
                edges[e.to].get(e.rev).cap += flow;
                return flow;
            }
        }
        return 0;
    }

    public static long dinic(int s, int t)
    {
        level = new int[edges.length];
        iter = new int[edges.length];
        long flow = 0;
        while (bfs(s, t))
        {
            Arrays.fill(iter, 0);
            long f;
            while ((f = dfs(s, t, LINF)) > 0)
            {
                flow += f;
            }
        }
        return flow;
    }

    public static void addEdge(int f, int t, long c)
    {
        edges[f].add(new Edge(t, c, edges[t].size()));
        edges[t].add(new Edge(f, 0, edges[f].size() - 1));
    }

    static class Edge
    {
        int to, rev;
        long cap;

        Edge(int to, long cap, int rev)
        {
            this.to = to;
            this.cap = cap;
            this.rev = rev;
        }
    }