CFR 730 I. Olympiad in Programming and Sports ( MCMF )
題意:
有兩個屋子,容量分別為 P, S。
有 N 個人,他們會各自選擇一個屋子進去。
第 i 個人對屋子 A 的喜好度是 A[ i ],對屋子 B 的喜好度是 B[ i ]。
輸出方案,使得滿意程度 ( 選擇的屋子的喜好度 ) 總和最大。
制約:
2 ≤ N ≤ 3000
P + S ≤ N
1 ≤ A[ i ], B[ i ] ≤ 3000
解法:
最小費用最大流。
人作為左邊一排的節點,兩個屋子右邊一排。
源點到每個人連容量 1 費用 0 的弧。
i 號人對屋子 A 連容量 1 費用 -A[ i ] 的弧,對屋子 B 同理。
屋子 A 對匯點連容量 P 費用 0 的弧,屋子 B 同理。
複雜度:
O( N**2 )
#include <bits/stdc++.h> using namespace std; template< class TF, class TC > struct CostFlow { static const int MAXV = 10000; static const TC INF = 0x3f3f3f3f; 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 = 3000; int N, P, S; int A[ MAXN ]; int B[ MAXN ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> P >> S; for( int i = 0; i < N; ++i ) { cin >> A[ i ]; } for( int i = 0; i < N; ++i ) { cin >> B[ i ]; } CostFlow< int, int > mcmf( N + 2 + 2, N + 2, N + 2 + 1 ); for( int i = 0; i < N; ++i ) { mcmf.add_edge( N + 2, i, 1, 0 ); mcmf.add_edge( i, N, 1, -A[ i ] ); mcmf.add_edge( i, N + 1, 1, -B[ i ] ); } mcmf.add_edge( N, N + 2 + 1, P, 0 ); mcmf.add_edge( N + 1, N + 2 + 1, S, 0 ); cout << -mcmf.flow().second << endl; for( int i = 0, cnt = 0; i < N; ++i ) { for( int j = 0; j < mcmf.E[ i ].size(); ++j ) if( mcmf.E[ i ][ j ].v == N ) { if( mcmf.E[ i ][ j ].f == 0 ) { cout << i + 1 << " \n"[ ++cnt == P ]; } } } for( int i = 0, cnt = 0; i < N; ++i ) { for( int j = 0;j < mcmf.E[ i ].size(); ++j ) if( mcmf.E[ i ][ j ].v == N + 1 ) { if( mcmf.E[ i ][ j ].f == 0 ) { cout << i + 1 << " \n"[ ++cnt == S ]; } } } return 0; }