D - 買い物上手 AtCoder Regular Contest 031

D: 買い物上手 - AtCoder Regular Contest 031 | AtCoder

問題概略
アイテムの値段と、組み合わせによって得られる経験値の一覧が与えられる。
アイテムをいくつか買い、得られた経験値÷使ったお金を最大化せよ。

1≦N≦100　1≦N≦100
N M
S1 S2 ... SN
T1 T2 ... TM
K1 A1,1 A1,2 ... A1,K1
K2 A2,1 A2,2 ... A2,K2
:
KN AN,1 AN,2 ... AN,KN

解法
いくつか選ぶのでフロー。
蟻本に平均の最大化について乗ってましたね。それチックで。
sum(exp) / sum(mon) >= x
sum(exp) - sum(mon) * x >= 0
これをフローにするのが難しいんですよね
とりあえず経験値のリストからアイテムへ辺をつなぎたい。

この選択をしたらこれらに影響があるって時によくやるかも

あとわかる情報を追加したい

↓これとか

sum(exp) - sum(mon) * x >= 0

とりあえずフローが完成したので使い方を考える。

よくよく見ると与えられた経験値をお金で割っている形になっている。

気をつけないといけないとのは与えられたフローが全て流れるように、xを増やすのではなく減らすところ。

二分法で解ける

類題

D: 切り分けできるかな？ - AtCoder Regular Contest 013 | AtCoder

解法

static int N, M, K;
    static int[] S, T;
    static ArrayList<Integer>[] A;

    public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        M = sc.nextInt();
        S = sc.nextIntArray(N);
        T = sc.nextIntArray(M);
        A = Stream.generate(ArrayList::new).limit(N).toArray(ArrayList[]::new);
        for (int i = 0; i < N; i++)
        {
            K = sc.nextInt();
            for (int j = 0; j < K; j++)
            {
                A[i].add(sc.nextInt() - 1);
            }
        }
        double ok = 0, ng = 1e9;
        for (int i = 0; i < 100; i++)
        {
            double x = (ok + ng) / 2;
            if (chk(x)) ng = x;
            else ok = x;
        }
        System.out.println(binarysearch(1e9, 0));

    }

    //条件を満たす最大値、あるいは最小値を求める
    static double binarysearch(double ok, double ng)
    {
        //int ok = 0; //解が存在する
        //int ng = N; //解が存在しない
        for (int i = 0; i < 100; i++)
        {
            double mid;
            if (ok < 0 && ng > 0 || ok > 0 && ng < 0) mid = (ok + ng) / 2;
            else mid = ok + (ng - ok) / 2;

            if (chk(mid))
            {
                ok = mid;
            }
            else
            {
                ng = mid;
            }
        }
        return ok;
    }

    static boolean chk(double x)
    {
        edges = Stream.generate(ArrayList::new).limit(N + M + 2).toArray(ArrayList[]::new);
        int s = N + M;
        int t = N + M + 1;
        for (int i = 0; i < N; i++) addEdge(s, i, S[i]);
        for (int i = 0; i < M; i++) addEdge(i + N, t, (double) T[i] * x);
        for (int i = 0; i < N; i++)
            for (Integer j : A[i])
                addEdge(i, N + j, INF);
        double f = dinic(s, t);
        double sm = 0;
        for (int i = 0; i < N; i++) sm += S[i];
        return sm <= f;
    }

    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 double dfs(int v, int t, double 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])
            {
                double 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 double dinic(int s, int t)
    {
        level = new int[edges.length];
        iter = new int[edges.length];
        double flow = 0;
        while (bfs(s, t))
        {
            Arrays.fill(iter, 0);
            double f;
            while ((f = dfs(s, t, LINF)) > 0)
            {
                flow += f;
            }
        }
        return flow;
    }

    public static void addEdge(int f, int t, double 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;
        double cap;

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