test/aoj/0424.test.cpp

• View this file on GitHub
• Last update: 2020-10-27 16:27:26+09:00
• Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0424

Depends on

• matching/hopcroft_karp.cpp

Code

// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0424

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#include "../../matching/hopcroft_karp.cpp"
#undef call_from_test

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

  int n;
  cin>>n;
  vector<string> ss(n);
  for(int i=0;i<n;i++) cin>>ss[i];

  int L=0,R=0;
  map<string, int> mp;
  for(int i=0;i<n;i++){
    if(ss[i].size()&1){
      mp[ss[i]]=L++;
    }else{
      mp[ss[i]]=R++;
    }
  }

  HopcroftKarp G(L,R);
  for(int i=0;i<n;i++){
    int m=ss[i].size();
    for(int j=0;j<m;j++){
      string t(ss[i]);
      t.erase(t.begin()+j);
      if(!mp.count(t)) continue;
      int u=mp[ss[i]],v=mp[t];
      if(t.size()&1) swap(u,v);
      G.add_edge(u,v);
    }
  }

  cout<<G.build()<<endl;
  return 0;
}

#line 1 "test/aoj/0424.test.cpp"
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0424

#include <bits/stdc++.h>
using namespace std;

#define call_from_test
#line 1 "matching/hopcroft_karp.cpp"

#line 3 "matching/hopcroft_karp.cpp"
using namespace std;
#endif
//BEGIN CUT HERE
// O(E \sqrt V)
struct HopcroftKarp{
  int L,R;
  vector< vector<int> > G;
  vector<int> match,level;

  HopcroftKarp(int L,int R):
    L(L),R(R),G(L+R),match(L+R,-1),level(L+R){}

  void add_edge(int u,int v){
    G[u].emplace_back(v+L);
    G[v+L].emplace_back(u);
  }

  bool bfs(){
    fill(level.begin(),level.end(),-1);
    queue<int> que;
    for(int i=0;i<L;i++){
      if(~match[i]) continue;
      level[i]=0;
      que.emplace(i);
    }
    bool found=false;
    while(!que.empty()){
      int v=que.front();que.pop();
      for(int u:G[v]){
        if(~level[u]) continue;
        level[u]=level[v]+1;
        int w=match[u];
        if(w==-1){
          found=true;
          continue;
        }
        if(~level[w]) continue;
        level[w]=level[u]+1;
        que.emplace(w);
      }
    }
    return found;
  }

  bool dfs(int v){
    for(int u:G[v]){
      if(level[v]+1!=level[u]) continue;
      level[u]=-1;
      int w=match[u];
      if(w<0 or dfs(w)){
        match[v]=u;
        match[u]=v;
        level[v]=-1;
        return true;
      }
    }
    level[v]=-1;
    return false;
  }

  int build(){
    int res=0;
    while(bfs())
      for(int i=0;i<L;i++)
        if(match[i]<0 and dfs(i))
          res++;
    return res;
  }

};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif
#line 8 "test/aoj/0424.test.cpp"
#undef call_from_test

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

  int n;
  cin>>n;
  vector<string> ss(n);
  for(int i=0;i<n;i++) cin>>ss[i];

  int L=0,R=0;
  map<string, int> mp;
  for(int i=0;i<n;i++){
    if(ss[i].size()&1){
      mp[ss[i]]=L++;
    }else{
      mp[ss[i]]=R++;
    }
  }

  HopcroftKarp G(L,R);
  for(int i=0;i<n;i++){
    int m=ss[i].size();
    for(int j=0;j<m;j++){
      string t(ss[i]);
      t.erase(t.begin()+j);
      if(!mp.count(t)) continue;
      int u=mp[ss[i]],v=mp[t];
      if(t.size()&1) swap(u,v);
      G.add_edge(u,v);
    }
  }

  cout<<G.build()<<endl;
  return 0;
}

Back to top page