最小点被覆 minimum vertex cover 2部グラフなら最大マッチングで解ける

Quiz

AC

解説

  • ワーシャルフロイドで最短距離を求め、アルファベットの条件を満たす頂点間を辺でつないだ新たなグラフGを考える
  • Gはアルファベットの条件から2部グラフ
  • 最小点被覆の位置に罠を置けばいい

その他

  • コンテスト中はvertex coverを全く考えなかったので葉の隣に罠を置いたりした
  • それだと輪っかの時に置けないので、輪っか状態なら適当に置いたりもした
  • そういうその場しのぎ的な解法では全ACは取れず

最大流ライブラリ

code

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

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

    vector<char> C(N);
    rep(i,N)cin>>C[i];

    // edge
    VI A(M);
    VI B(M);
    rep(i,M){
      cin>>A[i]>>B[i];
      A[i]--;
      B[i]--;
    }

    WarshallFloyd wa(N);
    rep(i,M){
      wa.register_edge2(A[i],B[i],1);
    }
    wa.calc();

    // start => (a,c,e) => (b,d,f) => end
    // と流れるようにする
    MaxFlow flow(N+2);
    ll start = N;
    ll end = N+1;
    rep(i,N){
      FOR(j,i+1,N){
        if(wa.distance(i,j)<=K and next(C[i],C[j])){
          // 辺をはれる
          ll v = C[i]-'a';
          if(v%2==0){
            flow.add_edge(i, j, 1);
          }else{
            flow.add_edge(j, i, 1);
          }
        }
      }
    }
    rep(i,N){
      ll v = C[i]-'a';
      if(v%2==0){
        flow.add_edge(start, i, 1);
      }else{
        flow.add_edge(i, end, 1);
      }
    }

    ll max_flow = flow.calc(start, end);
    p(max_flow);
    
    return 0;
}

HUPC2020Day1, Day2, Day3

Day2 (Aizu Set)

Day3 (Yushi Set)

D. Maximum Distance

1800 MST
  • Quiz
  • AC
  • 問題理解
    • 最初、max, min, cost, distanceで混乱した
    • costについては「経路上の1番高いコストの切符を買えば、他は無料」と考える
    • speciall vertexについては「見所」と考える。各見所から他の見所の全てに行きたい時、いくら持っていればいいか。それをspecial vertext各点について求める
  • 解説
    • MSTを作る
    • MSTに採用された各辺について、頂点A側、頂点B側のそれぞれにspecial vertexがあるなら、その辺は答えの対象になる
  • 解説2
    • MSTを作る時は辺コストが低い順に採用していくが、採用してUnionFindでいうuniteした時に、グループごとのspecial vertexの数も統合することにする（各グループの根に集めるとする）
    • uniteを続けるといずれspecial vertexの数 == Kとなり、その時の辺のコストが答え
struct Edge{
    ll from;
    ll to;
    ll cost;
    Edge(ll from, ll to, ll cost): from(from), to(to), cost(cost) {}
    bool operator<(const Edge &another) const
    {
        return cost < another.cost;
    }
    bool operator>(const Edge &another) const
    {
        return cost > another.cost;
    }
};

struct UnionFind{
    vector<ll> parent;
    UnionFind(ll sz){
        parent.resize(sz);
        reset();
    }

    void reset(){
        FOR(i, 0, parent.size()){
            parent[i] = i;
        }
    }

    void unite(ll a, ll b){
        if(a>b){
            swap(a, b);
        }
        ll rootA = findRoot(a);
        ll rootB = findRoot(b);
        if(rootA>rootB){
            swap(rootA, rootB);
        }
        if(rootA==rootB){
            return;
        }else{
            // 小さい方を親にする
            parent[rootB] = rootA;
        }
    }

    ll findRoot(ll a){
        if(parent[a]==a){
            return a;
        }else{
            return parent[a] = findRoot(parent[a]);
        }
    }

    map<ll, vector<ll> > getGroups(){
        map<ll, vector<ll> > G;
        FOR(i, 0, parent.size()){
            ll r = findRoot(i);
            G[r].push_back(i);
        }
        return G;
    }

    bool is_same_group(ll a, ll b){
        ll rootA = findRoot(a);
        ll rootB = findRoot(b);
        if(rootA==rootB){
            return true;
        }else{
            return false;
        }
    }
};

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

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

    // special
    VI X(K);
    rep(i,K){
      cin>>X[i];
      X[i]--;
    }

    // コストの小さい順に取り出す設定
    priority_queue<Edge, vector<Edge>, greater<Edge> > que;
    
    // edge
    rep(i,M){
      ll a,b,c;
      cin>>a>>b>>c;
      a--;b--;
      que.push(Edge(a,b,c));
    }

    UnionFind uf(N);
    
    // special vertex count (mergeする)
    VI C(N);
    for(ll x : X) C[x]=1;
    debug(C);

    // MST
    while(!que.empty()){
      auto edge = que.top(); que.pop();

      ll fr = edge.from;
      ll to = edge.to;

      if(!uf.is_same_group(fr, to)){
        ll r0 = uf.findRoot(fr);
        ll r1 = uf.findRoot(to);

        uf.unite(fr, to);

        ll r2 = uf.findRoot(fr);

        if(r0==r2){
          C[r2] += C[r1];
          C[r1]=0;
        }else{
          C[r2] += C[r0];
          C[r0]=0;
        }

        if(C[r2]==K){
          VI Ans;
          rep(i,K) Ans.push_back(edge.cost);
          print_vector(Ans);
          return 0;
        }
      }
    }
    p(-1);
    
    return 0;
}