# HE Zulu and Alarm Clock ( MCMF )

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

T 筆測資。
N 個鬧鐘，K 個時間。

1≤T≤2
1≤N≤50
1≤K≤17

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;
}
```