CFR 589 F. Gourmet and Banquet ( Flow, Binary Search )
題意:
有 N 種菜,你想要全部都吃一樣多的時間。
第 i 道菜可以吃的時間是 [ A[ i ], B[ i ] )。
只能在整數區間內吃菜,而且是至多一道。
問你最多可以吃多久時間。
制約:
1 ≤ N ≤ 100
0 ≤ A[ i ] < B[ i ] ≤ 10000
解法:
二分搜答案,每次重新建圖。
對於這種區間問題,很常用的技巧是離散化端點。
將有用的端點離散化出來之後,把每節都當作一個節點,通往匯點的容量是它的長度。
源點到每道菜建弧,容量是二分搜的值。
第 i 道菜對代表 [ A[ i ], B[ i ] ) 的每一小節的節點連邊,容量是無限大。
如果最大流等於 N * 二分搜的值,就代表這是可行的。
複雜度:
O( O( Dinic's ) * lg MAXB )
#include <bits/stdc++.h> using namespace std; template< class T > struct Dinic { static const int MAXV = 10000; static const T INF = 0x3f3f3f3f; 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, bool bidirectional = false ) { E[ u ].emplace_back( v, f, E[ v ].size() ); E[ v ].emplace_back( u, 0, E[ u ].size() - 1 ); if( bidirectional ) { E[ v ].emplace_back( u, f, 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 = 100; int N; int A[ MAXN ], B[ MAXN ]; vector< int > dsctz; signed main() { ios::sync_with_stdio( 0 ); cin >> N; for( int i = 0; i < N; ++i ) { cin >> A[ i ] >> B[ i ]; dsctz.emplace_back( A[ i ] ); dsctz.emplace_back( B[ i ] ); } sort( dsctz.begin(), dsctz.end() ); dsctz.erase( unique( dsctz.begin(), dsctz.end() ), dsctz.end() ); int lb = 0, ub = 10000 + 1; while( lb + 1 != ub ) { int mid = lb + ub >> 1; int SOURCE = N + dsctz.size(), SINK = N + dsctz.size() + 1; Dinic< int > din( SINK + 1, SOURCE, SINK ); for( int i = 0; i < N; ++i ) { din.add_edge( SOURCE, i, mid ); for( int j = 1; j < dsctz.size(); ++j ) { if( A[ i ] <= dsctz[ j - 1 ] and dsctz[ j ] <= B[ i ] ) { din.add_edge( i, N + j, din.INF ); } } } for( int i = 1; i < dsctz.size(); ++i ) { din.add_edge( N + i, SINK, dsctz[ i ] - dsctz[ i - 1 ] ); } ( din.flow() == mid * N ? lb : ub ) = mid; } cout << lb * N << endl; return 0; }