CFR 434 D. Nanami's Power Plant ( Flow, Mincut )
題意:
有 N 個二次函數,以及 M 條不等式。
你想要最大化所有二次函數的輸出的總和。
對於第 i 個二次函數,參數範圍是 [ L[ i ], R[ i ] ] 的整數。
第 i 條不等式表示 X[ U[ i ] ] ≤ X[ V[ i ] ] + D[ i ]。
問最大輸出總和。
制約:
1 ≤ N ≤ 50
0 ≤ M ≤ 100
abs( A ) ≤ 10
abs( B ), abs( C ) ≤ 1000
- 100 ≤ L[ i ] ≤ R[ i ] ≤ 100
解法:
如果把 N 個函數分別看成 N 條線,源點連到左端點,右端點連到匯點,每個可行參數都做一個邊,容量是對應的輸出,那麼就等價於求對每條線只能切一刀的最大割。把所有容量轉為負值之後,平移使得最小值非負就可以轉換成最小割問題。這樣做的目的在於可以有效地表示不等式的條件。
考慮一個不等式 X[ u ] ≤ X[ v ] + d,那代表第 u 條線如果取參數 [ s, ∞ ],那麼第 v 條線就不能取參數 [ -∞, s - d - 1 ]。因此如果給第 u 條線這個參數 s 代表的邊連容量無限大的弧到第 v 條線 s - d - 1 代表的邊的話,如果第 u 條線取參數 [ s, ∞ ],第 v 條線卻取 [ -∞, s - d - 1 ] 就會有流,得不到割。
#include <bits/stdc++.h> using namespace std; template< class T > struct Dinic { static const int MAXV = 20000; static constexpr T INF = 1e9; struct Edge { int v; T f; int re; Edge( int _v, T _f, int _re ): v( _v ), f( _f ), re( _re ) {} }; int n, s, t, level[ MAXV ]; vector< Edge > E[ MAXV ]; int now[ MAXV ]; Dinic( int _n, int _s, int _t ): n( _n ), s( _s ), t( _t ) {} void add_edge( int u, int v, T f ) { E[ u ].emplace_back( v, f, E[ v ].size() ); E[ v ].emplace_back( u, 0, E[ u ].size() - 1 ); } bool BFS() { memset( level, -1, sizeof( level ) ); queue< int > que; que.emplace( s ); level[ s ] = 0; while( not que.empty() ) { int u = que.front(); que.pop(); for( auto it: E[ u ] ) { if( it.f > 0 and level[ it.v ] == -1 ) { level[ it.v ] = level[ u ] + 1; que.emplace( it.v ); } } } return level[ t ] != -1; } T DFS( int u, T nf ) { if( u == t ) return nf; T res = 0; while( now[ u ] < E[ u ].size() ) { Edge &it = E[ u ][ now[ u ] ]; if( it.f > 0 and level[ it.v ] == level[ u ] + 1 ) { T tf = DFS( it.v, min( nf, it.f ) ); res += tf; nf -= tf; it.f -= tf; E[ it.v ][ it.re ].f += tf; if( nf == 0 ) return res; } else ++now[ u ]; } if( not res ) level[ u ] = -1; return res; } T flow( T res = 0 ) { while( BFS() ) { T temp; memset( now, 0, sizeof( now ) ); while( temp = DFS( s, INF ) ) { res += temp; res = min( res, INF ); } } return res; } }; const int MAXN = 50; const int MAXM = 100; int N, M; int A[ MAXN ], B[ MAXN ], C[ MAXN ]; int L[ MAXN ], R[ MAXN ]; int base[ MAXN + 1 ]; // node count before this wire int U[ MAXM ], V[ MAXM ], D[ MAXM ]; const int MAXF = 201000; // f( x ) = 10 * 100**2 + 1000 * 100 + 1000 yori signed main() { ios::sync_with_stdio( false ); cin >> N >> M; for( int i = 0; i < N; ++i ) { cin >> A[ i ] >> B[ i ] >> C[ i ]; } for( int i = 0; i < N; ++i ) { cin >> L[ i ] >> R[ i ]; base[ i + 1 ] = base[ i ] + R[ i ] - L[ i ] + 2; } int SRC = base[ N ], DST = SRC + 1; Dinic< int > din( base[ N ] + 2, SRC, DST ); for( int i = 0; i < N; ++i ) { din.add_edge( SRC, base[ i ], din.INF ); for( int j = L[ i ]; j <= R[ i ]; ++j ) { static auto f = [ & ]( int i, int x ) { return A[ i ] * x * x + B[ i ] * x + C[ i ]; }; din.add_edge( base[ i ] + j - L[ i ], base[ i ] + j - L[ i ] + 1, MAXF - f( i, j ) ); } din.add_edge( base[ i ] + R[ i ] - L[ i ] + 1, DST, din.INF ); } for( int i = 0; i < M; ++i ) { int u, v, d; cin >> u >> v >> d; --u, --v; for( int j = L[ u ]; j <= R[ u ]; ++j ) { // kocci no torieru sentaku wo rekkyo situtu if( L[ v ] <= j - d - 1 and j - d - 1 <= R[ v ] ) { // taisyou to suru mono ni toccya iken mono ga torieru baai din.add_edge( base[ u ] + j - L[ u ], base[ v ] + j - d - L[ v ], din.INF ); // fusegimasu } } } cout << N * MAXF - din.flow() << endl; return 0; }