CFR 164 C. Machine Programming ( MCMF )

題意：
你有 K 個機器，可以獨立處理任務。
你有 N 個任務可以選擇接或不接。
任務 i 需要在 [ S[ i ], T[ i ] ) 期間佔用一個機器，價值為 C[ i ]。
問最大總價值。

制約：
1 ≤ N ≤ 1000
1 ≤ K ≤ 50
1 ≤ S[ i ], T[ i ] ≤ 1e9
1 ≤ C[ i ] ≤ 1e6

解法：
區間問題，離散端點，MCMF 亂流。
左邊一排代表每一小節時段，右邊一排節點代表任務。
源點到第一個時段建弧，容量 K 費用 0。
對於所有 i，第 i 個時段對第 i + 1 個時段建弧，容量 K 費用 0。特別的，最後一個時段連到匯點。
對於第 i 個任務，從它對應的第一個時段建弧到代表它的節點，容量 1 費用 -C[ i ]，再從代表它的節點建弧到該任務結束的時段，容量 1 費用 0。

複雜度：
O( N * K )

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

int N, K;
int S[ MAXN ], T[ MAXN ], C[ MAXN ];
vector< int > dsctz;
map< int, int > dmp;

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> K;
  for( int i = 0; i < N; ++i ) {
    cin >> S[ i ] >> T[ i ] >> C[ i ];
    dsctz.emplace_back( S[ i ] );
    dsctz.emplace_back( S[ i ] + T[ i ] );
  }
  sort( dsctz.begin(), dsctz.end() );
  dsctz.erase( unique( dsctz.begin(), dsctz.end() ), dsctz.end() );
  for( int i = 0; i < dsctz.size(); ++i ) {
    dmp[ dsctz[ i ] ] = i;
  }
  CostFlow< int, int > mcmf( dsctz.size() + N + 2, dsctz.size() + N, dsctz.size() + N + 1 );
  mcmf.add_edge( dsctz.size() + N, 0, K, 0 );
  for( int i = 0; i + 1 < dsctz.size(); ++i ) {
    mcmf.add_edge( i, i + 1, K, 0 );
  }
  mcmf.add_edge( dsctz.size() - 1, dsctz.size() + N + 1, K, 0 );
  for( int i = 0; i < N; ++i ) {
    mcmf.add_edge( dmp[ S[ i ] ], dsctz.size() + i, 1, -C[ i ] );
    mcmf.add_edge( dsctz.size() + i, dmp[ S[ i ] + T[ i ] ], 1, 0 );
  }
  mcmf.flow();
  for( int i = 0; i < N; ++i ) {
    bool f = false;
    for( auto it: mcmf.E[ dsctz.size() + i ] ) if( it.v < dsctz.size() and dsctz[ it.v ] == S[ i ] + T[ i ] ) {
      f |= it.f == 0;
    }
    cout << f << " \n"[ i + 1 == N ];
  }
  return 0;
}