CFR 717 G. Underfail ( MCMF )
題意:
給長度 N 的字串 T。
有 M 種字串 S[],如果把第 i 個字串疊在 T 的上面重合,可以得到 P[ i ] 分。
對於 T 的所有位置,都不能有超過 X 個字符疊在上面。
問最大總得分。
制約:
1 ≤ N ≤ 500
1 ≤ M ≤ 100
1 ≤ P[ i ] ≤ 100
1 ≤ X ≤ 100
解法:
源點流到代表 T 的第一個位置的節點,容量 X 費用 0。
對所有 i,第 i 個位置留到第 i + 1 個位置,容量 X 費用 0。特別的,最後一個位置留到匯點。
對於一個位置 i,如果 T[ i : i + len( S[ x ] ) ) = S[ x ],那麼位置 i 對代表 S[ x ] 的節點建弧,容量 1 費用 -P[ i ],再從 S[ x ] 流回 i + len( S[ x ] )。
複雜度:
O( N * X )
#include <bits/stdc++.h> using namespace std; template< class TF, class TC > struct CostFlow { static const int MAXV = 10000; 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 = 500; const int MAXM = 100; int N; string T; int M; string S[ MAXM ]; int P[ MAXM ]; int X; signed main() { ios::sync_with_stdio( 0 ); cin >> N; cin >> T; cin >> M; for( int i = 0; i < M; ++i ) { cin >> S[ i ] >> P[ i ]; } cin >> X; CostFlow< int, int > mcmf( N + M + 2, N + M, N + M + 1 ); mcmf.add_edge( N + M, 0, X, 0 ); for( int i = 0; i + 1 < N; ++i ) { mcmf.add_edge( i, i + 1, X, 0 ); } mcmf.add_edge( N - 1, N + M + 1, X, 0 ); for( int i = 0; i < M; ++i ) { for( int j = 0; j + S[ i ].size() <= N; ++j ) { bool ng = false; for( int k = 0; k < S[ i ].size(); ++k ) if( S[ i ][ k ] != T[ j + k ] ) { ng = true; break; } if( ng ) continue; mcmf.add_edge( j, j + S[ i ].size() < N ? j + S[ i ].size() : N + M + 1, 1, -P[ i ] ); } } cout << -mcmf.flow().second << endl; return 0; }