CFR 277 E. Binary Tree on Plane ( MCMF )

Problem - 277E - Codeforces

題意：
有 N 個點在二維整數坐標上。
要求做一個二叉樹。
一個點 i 可以作為點 j 的父親，若且唯若 Y[ i ] > Y[ j ]。
問最小的邊長總和。若無解輸出 -1。

制約：
2 ≤ N ≤ 400
abs( X[ i ] ), abs( Y[ i ] ) ≤ 1000
所有點相異
容忍誤差 1e-6

解法：
非常難解釋，機智到嚇壞了。詳見代碼。
總之大概就是將流分成來自哪裡跟流到哪裡，流代表的是被上面的節點激發的數量。
只有被激發的點可以流到匯點一個單位，每個點至多只能被激發一次，這確保了最大流會對應樹。
費用在激發時收取。
一個點至多只能激發兩個值。

複雜度：
O( N**2 )

#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 = 400;

int N;
int X[ MAXN ], Y[ MAXN ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ) {
    cin >> X[ i ] >> Y[ i ];
  }
  CostFlow< int, double > mcmf( N + N + 2, N + N, N + N + 1 );
  for( int i = 0; i < N; ++i ) {
    mcmf.add_edge( N + N, i, 2, 0.0 );
    mcmf.add_edge( N + i, N + N + 1, 1, 0.0 );
    for( int j = 0; j < N; ++j ) if( Y[ i ] > Y[ j ] ) {
      auto sqr = [ & ]( int x ) { return x * x; };
      mcmf.add_edge( i, N + j, 1, sqrt( sqr( X[ i ] - X[ j ] ) + sqr( Y[ i ] - Y[ j ] ) ) );
    }
  }
  int flow;
  double cost;
  tie( flow, cost ) = mcmf.flow();
  if( flow == N - 1 ) cout << fixed << setprecision( 9 ) << cost << endl;
  else cout << -1 << endl;
  return 0;
}