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

フロー ライブラリ

f:id:peroon:20191107001407p:plain

Quiz

AC Code

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

解法

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

その他

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

最大流ライブラリ

// 最大流用の辺
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;
    }
};

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

  • 始点を０
  • 石を１～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 燃やす埋める）

2021年、E-MUL解き直し。雰囲気で解いていたのでハマった

  • AC
  • 説明
    • コードにもコメントしたが、注意ポイントが2つある
    • 注意ポイント1１にあるように、Aiが正のものだけ先に報酬を与える必要がある。Aiが負のものは「先に報酬」の工夫なしにグラフ上のペナルティとして表現できるので「先に報酬」は不要
  • N=2
    • 考えがあっているか確認するには、N=2の単純な場合を考えるといい
    • N=2, A=[5,-10]の場合
    • 1番目を残し、2番めを破壊すればいいのは自明。これをフローで表現できているか図示すると、下記のようになる
    • 赤い線を左から右に横切る辺のコストがペナルティとなることが分かる（なので中央の∞ペナルティはかからない）

f:id:peroon:20210305133455p:plain

#include <atcoder/maxflow>
using namespace atcoder; // 忘れがち

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    ll start=N;
    ll end=N+1;

    ll base=0;
    for(ll a : A){
      if(a>0) base+=abs(a); // 注意ポイント１：「正のものだけ」先に報酬を与える
    }

    mf_graph<ll> graph(N+2);

    rep(i,N){
      ll a = A[i];
      if(a>=0){
        graph.add_edge(start,i,a);
        graph.add_edge(i,end,0);
      }
      else{
        graph.add_edge(start,i,0);
        graph.add_edge(i,end,-a);
      }
    }

    rep(i,N){
      FOR(j,i+1,N){
        if(i==j)continue;
        ll a = i+1;
        ll b = j+1;
        if(b%a==0){
          graph.add_edge(j,i,inf); // 注意ポイント２：方向 (i->j or j->i)
        }
      }
    }
    ll fl = graph.flow(start,end);
    ll ans = base-fl;
    p(ans);
    
    return 0;
}