AOJ 2251 - Merry Christmas ~DAG上の最小パス被覆 minimum path cover~

f:id:peroon:20200924033756p:plain

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

// 入力:DAGなグラフG
// 出力:最小パス被覆
ll minimum_path_cover(VV& G){
  ll N = SZ(G);
  ll source = 2*N;
  ll sink = 2*N+1;
  mf_graph<ll> flow(2*N+2);

  rep(i,N){
    flow.add_edge(source,i,1);
    flow.add_edge(N+i,sink,1);
  }
  // 二重辺をはらないように注意
  rep(i,N){
    for(ll to : G[i]){
      flow.add_edge(i, to+N, 1);
    }
  }
  ll max_flow = flow.flow(source, sink);
  return N - max_flow;
}

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

    // input
    while(true){
      ll N,M,L;
      cin>>N>>M>>L;
      debug(N,M,L);
      if(N==0) return 0;

      auto wf = WarshallFloyd(N);
      
      // edge
      rep(i,M){
        ll a,b,c;
        cin>>a>>b>>c;
        wf.register_edge2(a,b,c);
      }
      wf.calc();

      // requests
      VI P(L);
      VI T(L);
      rep(i,L){
        cin>>P[i]>>T[i];
      }

      // リクエストiの後にリクエストjを処理できるなら辺
      // これはDAG
      VV G(L);
      rep(i,L){
        rep(j,L){
          if(i==j) continue;
          // move i to j
          ll a = P[i];
          ll b = P[j];
          ll d = wf.distance(a,b);
          if(T[i]+d<=T[j]){
            G[i].push_back(j);
          }
        }
      }

      ll ans = minimum_path_cover(G);
      p(ans);
    }
   
    return 0;
}