B. Valuable Paper ～Hopcroft–Karp algorithm～ 条件(capacity=1)付き2部マッチングでO(E sqrt(V))

• Quiz
  • https://codeforces.com/contest/1423/problem/B
• AC
  • https://codeforces.com/contest/1423/submission/99738013
• 解説
  • editorialの通り、使う辺のコストの最大値を上げるほど最大マッチング＝Nにしやすい（単調性）ので二分探索する
  • しかし最大流を使った2部マッチングでは間に合わない
  • Hopcroft–Karp algorithmというのがあり、各辺の容量が1の時はO(E sqrt(V))で解けるらしい
  • うしさんのライブラリを使って通した https://ei1333.github.io/algorithm/bipartite-matching.html

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

    // input
    ll N,M;
    cin>>N>>M;

    VI A(M);
    VI B(M);
    VI C(M);
    rep(i,M){
      cin>>A[i]>>B[i]>>C[i];
      A[i]--;
      B[i]--;
    }
    ll max_cost = MAX(C);

    // 辺コストをlimitまで制限した時のマッチング数を返す
    auto f = [&](ll limit){
      Bipartite_Matching graph(2*N, 2*N);
      rep(i,M){
        if(C[i]>limit)continue;
        graph.add_edge(A[i],B[i]+N);
      }
      return graph.bipartite_matching();
    };

    if(f(max_cost)<N){
      p(-1); return 0;
    }

    ll left = 0; // can't
    ll right = max_cost; // can
    while(left+1!=right){
      ll center = (left+right)/2;
      if(f(center)==N){
        right = center;
      }else{
        left = center;
      }
    }

    p(right);
   
    return 0;
}