HE Zulu and Alarm Clock ( MCMF )

https://www.hackerearth.com/problem/algorithm/zulu-and-alarm-clock-1/

題意：
T 筆測資。
N 個鬧鐘，K 個時間。
你要把 K 個鬧鐘調成這 K 個時間。
你可以上下調整時、秒、分，會進位退位。
問最小調整次數。

制約：
1≤T≤2
1≤N≤50
1≤K≤17

解法：
可以用遮罩動態規劃亂搞。
但是直覺很 MCMF。
先跑一遍最短路徑，給鬧鐘和目標時間建弧，費用就是最短路徑。
MCMF 亂流。

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

template< class TF, class TC >
struct CostFlow {
  static const int MAXV = 205;
  static const TC INF = 0x3f3f3f3f;
  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 };
  }
};

int N, K;
tuple< int, int, int > clk[ 50 ];
tuple< int, int, int > ala[ 17 ];

tuple< int, int, int > convert( string s ) {
  return make_tuple( stoi( s.substr( 0, 2 ) ), stoi( s.substr( 3, 2 ) ), stoi( s.substr( 6, 2 ) ) );
}

tuple< int, int, int > tick( tuple< int, int, int > u, int x, int d ) {
  int c[ 3 ];
  tie( c[ 0 ], c[ 1 ], c[ 2 ] ) = u;
  c[ x ] += d;
  for( int i = 3 - 1; i >= 0; --i ) {
    if( i ) {
      if( c[ i ] < 0 ) {
        c[ i ] += 60;
        --c[ i - 1 ];
      } else if( c[ i ] >= 60 ) {
        c[ i ] -= 60;
        ++c[ i - 1 ];
      }
    } else {
      if( c[ i ] < 0 ) {
        c[ i ] += 24;
      } else if( c[ i ] >= 24 ) {
        c[ i ] -= 24;
      }
    }
  }
  return make_tuple( c[ 0 ], c[ 1 ], c[ 2 ] );
}

void sssp( CostFlow< int, int > &mcmf, int si ) {
  static int dis[ 24 ][ 60 ][ 60 ];
  memset( dis, 0x3f, sizeof( dis ) );
  queue< pair< int, tuple< int, int, int > > > que;
  que.emplace( 0, clk[ si ] );
  while( not que.empty() ) {
    int d;
    tuple< int, int, int > u;
    tie( d, u ) = que.front();
    que.pop();
    for( int i = 0; i < 3; ++i ) {
      for( int j = -1; j <= 1; ++j ) if( j != 0 ) {
        tuple< int, int, int > v = tick( u, i, j );
        int a, b, c;
        tie( a, b, c ) = v;
        if( dis[ a ][ b ][ c ] <= d + 1 ) continue;
        que.emplace( dis[ a ][ b ][ c ] = d + 1, v );
      }
    }
  }
  for( int i = 0; i < K; ++i ) {
    int a, b, c;
    tie( a, b, c ) = ala[ i ];
    mcmf.add_edge( si, N + i, 1, dis[ a ][ b ][ c ] );
  }
}

signed main() {
  ios::sync_with_stdio( 0 );
  int T;
  cin >> T;
  for( int ti = 0; ti < T; ++ti ) {
    cin >> N >> K;
    for( int i = 0; i < N; ++i ) {
      string s;
      cin >> s;
      clk[ i ] = convert( s );
    }
    for( int i = 0; i < K; ++i ) {
      string s;
      cin >> s;
      ala[ i ] = convert( s );
    }
    int SOURCE = N + K;
    int SINK = N + K + 1;
    CostFlow< int, int > mcmf( N + K + 2, SOURCE, SINK );
    for( int i = 0; i < N; ++i ) {
      mcmf.add_edge( SOURCE, i, 1, 0 );
    }
    for( int i = 0; i < K; ++i ) {
      mcmf.add_edge( N + i, SINK, 1, 0 );
    }
    for( int i = 0; i < N; ++i ) {
      sssp( mcmf, i );
    }
    cout << mcmf.flow().second << endl;
  }
  return 0;
}