This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// 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; }