D - 浮気予防 (abc010_4) 最大フロー・最小カット

Quiz

https://atcoder.jp/contests/abc010/tasks/abc010_4

Submit

https://atcoder.jp/contests/abc010/submissions/4065384

• 意外とTLEにもならず一発で通って良かった
• パスを何度も求めるのを関数化したのが良かった
  • 見やすい
  • 変数名の自由度が上がる

学び

• 最小カットとして捉えられるように終端ノードを足す
• 最大フロー = 最小カット
• 最大フローの求め方

流してCapacityを更新

逆流するとは、流れをつなぎかえるということ

参考

http://www.hongo.wide.ad.jp/~jo2lxq/dm/lecture/09.pdf

2020/10/31

• 再度解いた。有向辺ではなく両方向にadd_edgeしないとWAになった
• https://atcoder.jp/contests/abc010/submissions/17748799

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

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

    // input
    ll N,G,E;
    cin>>N>>G>>E;

    VI P(G);
    rep(i,G)cin>>P[i];

    mf_graph<ll> graph(N+1);
    ll start=0;
    ll end=N;

    // edge
    rep(i,E){
      ll a,b;cin>>a>>b;
      graph.add_edge(a,b,1);
      graph.add_edge(b,a,1); // 両方向！
    }
    // girl to sink
    rep(i,G){
      graph.add_edge(P[i],end,1);
      graph.add_edge(end,P[i],1); // 両方向！
    }

    ll flow = graph.flow(start,end);
    chmin(flow, G);

    p(flow);
    
    return 0;
}