CFR 491 C. Deciphering ( MCMF )
題意:
給你長度 N 的字串 A 以及字串 B。
你可以做一組字母對字母的一對一映射,使得同位置相符的字符數量最多。
制約:
1 ≤ N ≤ 2e6
1 ≤ K ≤ 52
解法:
MCMF 亂流。
映射前映射後。
源點建弧到映射前的容量是 1,費用是映射前的該字母的數量。
映射後到匯點同理。
映射前到映射後的即是匹配數量。
複雜度:
O( K ** 2 )
#include <bits/stdc++.h> using namespace std; template< class TF, class TC > struct CostFlow { static const int MAXV = 20000; static constexpr TC INF = 1e9; struct Edge { int v, r; TF f; TC c; Edge( int _v, int _r, TF _f, TC _c ): v( _v ), r( _r ), f( _f ), c( _c ) {} }; int n, s, t, pre[ MAXV ], pre_E[ MAXV ], inq[ MAXV ]; TF fl; TC dis[ MAXV ], cost; vector< Edge > E[ MAXV ]; CostFlow( int _n, int _s, int _t ): n( _n ) ,s( _s ), t( _t ), fl( 0 ), cost( 0 ) {} void add_edge( int u, int v, TF f, TC c ) { E[ u ].emplace_back( v, E[ v ].size(), f, c ); E[ v ].emplace_back( u, E[ u ].size() - 1, 0, -c ); } pair< TF, TC > flow() { while( true ) { for( int i = 0; i < n; ++i ) { dis[ i ] = INF; inq[ i ] = 0; } dis[ s ] = 0; queue< int > que; que.emplace( s ); while( not que.empty() ) { int u = que.front(); que.pop(); inq[ u ] = 0; for( int i = 0; i < E[ u ].size(); ++i ) { int v = E[ u ][ i ].v; TC w = E[ u ][ i ].c; if( E[ u ][ i ].f > 0 and dis[ v ] > dis[ u ] + w ) { pre[ v ] = u; pre_E[ v ] = i; dis[ v ] = dis[ u ] + w; if( not inq[ v ] ) { inq[ v ] = 1; que.emplace( v ); } } } } if( dis[ t ] == INF ) break; TF tf = INF; for( int v = t, u, l; v != s; v = u ) { u = pre[ v ]; l = pre_E[ v ]; tf = min( tf, E[ u ][ l ].f ); } for( int v = t, u, l; v != s; v = u ) { u = pre[ v ]; l = pre_E[ v ]; E[ u ][ l ].f -= tf; E[ v ][ E[ u ][ l ].r ].f += tf; } cost += tf * dis[ t ]; fl += tf; } return { fl, cost }; } }; const int MAXN = int( 2e6 ); const int MAXK = 52; int N, K; string A; string B; int cost[ MAXK ][ MAXK ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> K; cin >> A; cin >> B; for( int i = 0; i < N; ++i ) { auto letter2val = [ & ]( int c ) { return 'a' <= c and c <= 'z' ? c - 'a' : 26 + c - 'A'; }; --cost[ letter2val( A[ i ] ) ][ letter2val( B[ i ] ) ]; } CostFlow< int, int > mcmf( 2 * K + 2, 2 * K, 2 * K + 1 ); for( int i = 0; i < K; ++i ) { mcmf.add_edge( 2 * K, i, 1, 0 ); for( int j = 0; j < K; ++j ) { mcmf.add_edge( i, K + j, 1, cost[ i ][ j ] ); } mcmf.add_edge( K + i, 2 * K + 1, 1, 0 ); } cout << -mcmf.flow().second << endl; for( int i = 0; i < K; ++i ) { for( int j = 0; j < mcmf.E[ i ].size(); ++j ) if( mcmf.E[ i ][ j ].f == 0 ) { auto val2letter = [ & ]( int x ) { return x < 26 ? char( 'a' + x ) : char( 'A' + x - 26 ); }; cout << val2letter( mcmf.E[ i ][ j ].v - K ); } } cout << endl; return 0; }