题解 P5769 【[JSOI2016]飞机调度】

chihik · 2020-07-19 21:16:04 · 题解

网络流24题

为了使飞机数量尽量少，一架飞机尽量多飞几趟航班。

将航班看成一个点，其实就是求最小路径覆盖。

如果 i,j 航班可以由一架飞机先后飞行，那么将 i,j 连一条边。

现在考虑如何判断可先后进行的航班。

可以用 \text{Floyd} 处理由机场 i 到 j ，且可以立即起飞的最短时间 dis(i,j)。

那么只需要满足：

Dinic需要加当前弧优化。 应该都知道吧。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

template<typename _T>
void Read( _T &x ) {
    x = 0; int f = 1;
    char s = getchar( );
    for( ; s < '0' || s > '9' ; s = getchar( ) ) f = s == '-' ? -f : f;
    for( ; s >= '0' && s <= '9' ; s = getchar( ) ) x = x * 10 + s - '0';
    x *= f;
}
template<typename _T>
void Write( _T x ) {
    if( x < 0 ) putchar( '-' ) , x = -x;
    if( x >= 10 ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

const int MAXN = 500 , MAXM = 260000;
struct node {
    int v , flow , nxt;
}Graph[ MAXM + 5 ];
int tot = 1 , Head[ 2 * MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
    Graph[ ++ tot ] = { v , f , Head[ u ] };
    Head[ u ] = tot;
}

int n , m , S , T , p[ MAXN + 5 ] , t[ MAXN + 5 ][ MAXN + 5 ] , dis[ MAXN + 5 ][ MAXN + 5 ];
int x[ MAXN + 5 ] , y[ MAXN + 5 ] , tim[ MAXN + 5 ];
int lev[ 2 * MAXN + 5 ] , cur[ 2 * MAXN + 5 ];
bool Layering( int s , int t ) {
    memset( lev , -1 , sizeof( lev ) );
    memcpy( cur , Head , sizeof( Head ) );
    queue< int > Que;
    Que.push( s ) , lev[ s ] = 0;
    while( !Que.empty( ) ) {
        int u = Que.front( ); Que.pop( );
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flow;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ t ] != -1;
}
int dfs( int u , int t , int f ) {
    if( u == t ) return f;
    for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
        int v = Graph[ i ].v , flw = Graph[ i ].flow;
        cur[ u ] = i;
        if( flw > 0 && lev[ v ] == lev[ u ] + 1 ) {
            int mf = dfs( v , t , min( f , flw ) );
            if( mf ) {
                Graph[ i ].flow -= mf; Graph[ i ^ 1 ].flow += mf;
                return mf;
            }
        }
    }
    return 0;
}
int Dinic( int s , int t ) {
    int Maxf = 0;
    while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
    return Maxf;
}
void MakeGraph( ) {
    S = 2 * m + 1 , T = 2 * m + 2;
    for( int i = 1 ; i <= m ; i ++ )
        Add_Edge( S , i , 1 ) , Add_Edge( i , S , 0 );
    for( int i = 1 ; i <= m ; i ++ )
        Add_Edge( i + m , T , 1 ) , Add_Edge( T , i + m , 0 );
    for( int i = 1 ; i <= m ; i ++ )
        for( int j = 1 ; j <= m ; j ++ )
            if( tim[ i ] + t[ x[ i ] ][ y[ i ] ] + p[ y[ i ] ] + dis[ y[ i ] ][ x[ j ] ] <= tim[ j ] )
                Add_Edge( i , j + m , 1 ) , Add_Edge( j + m , i , 0 );
}

void Floyd( ) {
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= n ; j ++ )
            if( i ^ j ) dis[ i ][ j ] = t[ i ][ j ] + p[ j ];
    for( int k = 1 ; k <= n ; k ++ )
        for( int i = 1 ; i <= n ; i ++ )
            for( int j = 1 ; j <= n ; j ++ )
                if( dis[ i ][ j ] > dis[ i ][ k ] + dis[ k ][ j ] )
                    dis[ i ][ j ] = dis[ i ][ k ] + dis[ k ][ j ];
}

int main( ) {
    Read( n ) , Read( m );
    for( int i = 1 ; i <= n ; i ++ )
        Read( p[ i ] );
    for( int i = 1 ; i <= n ; i ++ )
        for( int j = 1 ; j <= n ; j ++ )
            Read( t[ i ][ j ] );
    for( int i = 1 ; i <= m ; i ++ )
        Read( x[ i ] ) , Read( y[ i ] ) , Read( tim[ i ] );

    Floyd( );
    MakeGraph( );
    Write( m - Dinic( S , T ) ) , putchar('\n');
    return 0; 
}