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=2679 #include<bits/stdc++.h> using namespace std; #define call_from_test #include "../../mincostflow/primaldual.cpp" #undef call_from_test const int MAX = 52; struct ARR{ array<int, MAX> val; ARR(){fill(val.begin(),val.end(),0);} ARR(int x){fill(val.begin(),val.end(),x);} int& operator[](int k){return val[k];}; int operator[](int k)const{return val[k];}; ARR operator+(const ARR &oth) const{ ARR res; for(int i=0;i<MAX;i++) res[i]=val[i]+oth[i]; return res; } ARR operator-(const ARR &oth) const{ ARR res; for(int i=0;i<MAX;i++) res[i]=val[i]-oth[i]; return res; } ARR operator-() const{ ARR res; for(int i=0;i<MAX;i++) res[i]=-val[i]; return res; } ARR operator*(const int &k) const{ ARR res; for(int i=0;i<MAX;i++) res[i]=val[i]*k; return res; } ARR operator/(const int &k) const{ ARR res; for(int i=0;i<MAX;i++) res[i]=val[i]/k; return res; } bool operator< (const ARR &oth) const{ return val< oth.val; } bool operator> (const ARR &oth) const{ return val< oth.val; } bool operator==(const ARR &oth) const{ return val==oth.val; } }; namespace std { template<> class numeric_limits<ARR> { public: static ARR max() {return ARR(numeric_limits<int>::max());}; }; } int main(){ int n; cin>>n; vector<string> vs(n); for(int i=0;i<n;i++) cin>>vs[i]; auto enc=[&](char c){ if(isupper(c)) return c-'A'; return 26+c-'a'; }; auto dec=[&](int d){ if(d<26) return 'A'+d; return 'a'+d-26; }; int S=n*2,T=n*2+1; PrimalDual<int, ARR> G(n*2+2); for(int i=0;i<n;i++){ G.add_edge(S,i,1,ARR()); G.add_edge(n+i,T,1,ARR()); } const int INF = 1e5; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ARR cost(INF); cost[enc(vs[i][j])]=INF-1; G.add_edge(i,n+j,1,cost); } } assert(G.build(S,T,n)); auto res=G.get_cost(); string ans; for(int i=0;i<MAX;i++) for(int j=0;j<n*INF-res[i];j++) ans+=dec(i); cout<<ans<<endl; return 0; }
#line 1 "test/aoj/2679.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2679 #include<bits/stdc++.h> using namespace std; #define call_from_test #line 1 "mincostflow/primaldual.cpp" #line 3 "mincostflow/primaldual.cpp" using namespace std; #endif //BEGIN CUT HERE // O(F E \log V) template<typename Flow, typename Cost> struct PrimalDual{ struct Edge{ int dst; Flow cap; Cost cost; int rev; Edge(int dst,Flow cap,Cost cost,int rev): dst(dst),cap(cap),cost(cost),rev(rev){} }; vector<vector<Edge>> G; vector<Cost> h,dist; vector<int> prevv,preve; PrimalDual(int n):G(n),h(n),dist(n),prevv(n),preve(n){} void add_edge(int u,int v,Flow cap,Cost cost){ int e=G[u].size(); int r=(u==v?e+1:G[v].size()); G[u].emplace_back(v,cap,cost,r); G[v].emplace_back(u,0,-cost,e); } Cost residual_cost(int src,Edge &e){ return e.cost+h[src]-h[e.dst]; } void dijkstra(int s){ struct P{ Cost first; int second; P(Cost first,int second):first(first),second(second){} bool operator<(const P&a) const{return first>a.first;} }; priority_queue<P> pq; dist[s]=0; pq.emplace(dist[s],s); while(!pq.empty()){ P p=pq.top();pq.pop(); int v=p.second; if(dist[v]<p.first) continue; for(int i=0;i<(int)G[v].size();i++){ Edge &e=G[v][i]; if(e.cap==0) continue; if(!(dist[v]+residual_cost(v,e)<dist[e.dst])) continue; dist[e.dst]=dist[v]+e.cost+h[v]-h[e.dst]; prevv[e.dst]=v; preve[e.dst]=i; pq.emplace(dist[e.dst],e.dst); } } } Cost res; bool build(int s,int t,Flow f, function<void(decltype(h)&)> init=[](decltype(h) &p){ fill(p.begin(),p.end(),0); }){ res=0; init(h); const Cost INF = numeric_limits<Cost>::max(); while(f>0){ fill(dist.begin(),dist.end(),INF); dijkstra(s); if(dist[t]==INF) return false; for(int v=0;v<(int)h.size();v++) if(dist[v]<INF) h[v]=h[v]+dist[v]; Flow d=f; for(int v=t;v!=s;v=prevv[v]) d=min(d,G[prevv[v]][preve[v]].cap); f-=d; res=res+h[t]*d; for(int v=t;v!=s;v=prevv[v]){ Edge &e=G[prevv[v]][preve[v]]; e.cap-=d; G[v][e.rev].cap+=d; } } return true; } Cost get_cost(){return res;} }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 8 "test/aoj/2679.test.cpp" #undef call_from_test const int MAX = 52; struct ARR{ array<int, MAX> val; ARR(){fill(val.begin(),val.end(),0);} ARR(int x){fill(val.begin(),val.end(),x);} int& operator[](int k){return val[k];}; int operator[](int k)const{return val[k];}; ARR operator+(const ARR &oth) const{ ARR res; for(int i=0;i<MAX;i++) res[i]=val[i]+oth[i]; return res; } ARR operator-(const ARR &oth) const{ ARR res; for(int i=0;i<MAX;i++) res[i]=val[i]-oth[i]; return res; } ARR operator-() const{ ARR res; for(int i=0;i<MAX;i++) res[i]=-val[i]; return res; } ARR operator*(const int &k) const{ ARR res; for(int i=0;i<MAX;i++) res[i]=val[i]*k; return res; } ARR operator/(const int &k) const{ ARR res; for(int i=0;i<MAX;i++) res[i]=val[i]/k; return res; } bool operator< (const ARR &oth) const{ return val< oth.val; } bool operator> (const ARR &oth) const{ return val< oth.val; } bool operator==(const ARR &oth) const{ return val==oth.val; } }; namespace std { template<> class numeric_limits<ARR> { public: static ARR max() {return ARR(numeric_limits<int>::max());}; }; } int main(){ int n; cin>>n; vector<string> vs(n); for(int i=0;i<n;i++) cin>>vs[i]; auto enc=[&](char c){ if(isupper(c)) return c-'A'; return 26+c-'a'; }; auto dec=[&](int d){ if(d<26) return 'A'+d; return 'a'+d-26; }; int S=n*2,T=n*2+1; PrimalDual<int, ARR> G(n*2+2); for(int i=0;i<n;i++){ G.add_edge(S,i,1,ARR()); G.add_edge(n+i,T,1,ARR()); } const int INF = 1e5; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ARR cost(INF); cost[enc(vs[i][j])]=INF-1; G.add_edge(i,n+j,1,cost); } } assert(G.build(S,T,n)); auto res=G.get_cost(); string ans; for(int i=0;i<MAX;i++) for(int j=0;j<n*INF-res[i];j++) ans+=dec(i); cout<<ans<<endl; return 0; }