CFR 653 D. Delivery Bears ( Flow, Binary Search )

Problem - 653D - Codeforces

題意：
N 個節點 M 條有向邊的圖。有 X 隻熊。起點 1，終點 N。
這些熊要搬運貨物，如果一隻熊要搬運 W 單位，那麼其他所有熊也必須搬運 W 單位。
每條邊都有限制重量，也就是經過的重量總和不能超過它。
問可以搬運的最大總重量。

制約：
2 ≤ N ≤ 50
1 ≤ M ≤ 500
1 ≤ X ≤ 1e5
1 ≤ C[ i ] ≤ 1e6
輸出誤差 ≤ 1e-6

解法：
浮點數很麻煩，想辦法變成整數問題。
如果決定了一隻熊要搬運多少重量，那麼就能知道一個邊可以有多少隻熊經過。
由於解有單調性，對這個重量二分搜，每次重新建圖，如果最大流等於 X，就是可行的。
最後，二分搜採取 for( i <- 1..100 ) 比較不會出事.... 不明 while( fabs( .. ) < eps ) 哪裏爛了。

複雜度：
O( O( Dinic's ) * 100 )

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#pragma GCC optimize ("fast-math")

#include <bits/stdc++.h>
using namespace std;

template< class T >
struct Dinic {
  static const int MAXV = 50;
  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 = 50;
const int MAXM = 500;

int N, M, X;
int A[ MAXM ], B[ MAXM ], C[ MAXM ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M >> X;
  for( int i = 0; i < M; ++i ) {
    cin >> A[ i ] >> B[ i ] >> C[ i ];
    --A[ i ], --B[ i ];
  }
  double lb = 0.0, ub = 1e6;
  for( int i = 0; i < 100; ++i ) {
    double mid = ( lb + ub ) / 2;
    Dinic< int > din( N, 0, N - 1 );
    for( int i = 0; i < M; ++i ) {
      din.add_edge( A[ i ], B[ i ], min( C[ i ] / mid, 1e9 ) );
    }
    ( din.flow() >= X ? lb : ub ) = mid;
  }
  cout << fixed << setprecision( 7 ) << lb * X << endl;
  return 0;
}