perogram

E - MUL ~燃やす埋める・最大流・フロー flow~

f:id:peroon:20191107001407p:plain

Quiz

https://atcoder.jp/contests/arc085/tasks/arc085_c

AC Code

https://atcoder.jp/contests/arc085/submissions/8316327

解法

アルメリアさんの解説の通り

その他

  • 割る・残すは右左のどちらでもいい(今回たまたまアルメリアさんとは逆になった)
  • 罰金を最小化する問題に置き換えてフロー
  • 倍数の石は同時に割らなければ行けない条件を辺としてはる(4→2へinf、など)
    • 最初、2→4の方向で張ってしまって解答が合わず
    • ちゃんと考えるのもよし、逆向きで試してみるもよし

最大流ライブラリ

// 最大流用の辺
struct Edge{
    ll to;
    ll capacity;
    ll rev; // index
    Edge(ll t, ll c, ll r){
        to = t;
        capacity = c;
        rev = r;
    }
    Edge(){}
};
 
// 最大流
// ford fulkerson ver
struct MaxFlow{
    vector<vector<Edge> > G;
    vector<bool> used;
 
    MaxFlow(ll node_num){
        G.resize(node_num);
        used.resize(node_num);
    }
 
    void add_edge(ll from, ll to, ll capacity){
        G[from].push_back(Edge(to, capacity, G[to].size()));
        G[to].push_back(Edge(from, 0, G[from].size()-1));
    }
 
    ll dfs(ll v, ll t, ll flow){
        if(v==t) return flow;
        used[v] = true;
        for(Edge &edge : G[v]){
            if(!used[edge.to] && edge.capacity > 0){
                ll d = dfs(edge.to, t, min(flow, edge.capacity));
                if(d>0){
                    edge.capacity -= d;
                    G[edge.to][edge.rev].capacity += d;
                    return d;
                }
            }
        }
        return 0;
    }
 
    ll calc(ll start, ll end){
        ll flow_sum = 0;
        while(true){
            fill(ALL(used), false);
            ll f = dfs(start, end, inf);
            if(f==0){
                break;
            }
            flow_sum += f;
        }
        return flow_sum;
    }
};

最大流を実際に使っているコード

  • 始点を0
  • 石を1~N
  • 終点をN+1とした
    ll N; 
    cin >> N;

    VI A(N);
    rep(i, N){
        cin >> A.at(i);
    }

    MaxFlow flow(N+2);
    
    // 0 start
    // 1-N node
    // N+1 sink

    ll sum = 0;
    rep(i, N){
      ll id = i+1;
      ll a = A[i];

      if(a>=0){
        sum += a; // 無条件で貰えるお金
        flow.add_edge(0, id, a); // waru
        flow.add_edge(id, N+1, 0);
      }else{
        flow.add_edge(0, id, 0);
        flow.add_edge(id, N+1, -a);
      }
    }

    FOR(i, 1, N){
      // iの倍数へのエッジ
      FOR(m, 2, 101){
        if(i*m>N)break;
        flow.add_edge(m*i, i, inf);
      }
    }

    ll penalty = flow.calc(0, N+1);
    ll ans = sum - penalty;
    p(ans);

他の最大流を使う問題(not 燃やす埋める)