GCJ 2009 R2 pC. Stock Charts ( Bipartite Matching, Hungarian or Dinic )

Dashboard - Round 2 2009 - Google Code Jam
Let us first represent the relations of the charts by directing edges from chart A to chart B iff A can be laid under B on the same sheet of paper ( as the description says ) without interfering one another. It will form a DAG. We want to maxmize the number of ordered pairs ( u, v ), where there is an edge from u to v, and u does not belong to any other ordered pair as the first element nor does v belong to any other ordered pair as the second element. Thus it can be modelled as a bipartite problem, the objective then is to have maximum bipartite matching. This can be solved by Hungarian's, or max-flow algorithms such as Dinic's. Adding an extra source s and extra sink t, having s directed towards each node that directs out, and t being directed from each node that is directed in, the bipartite matching problem is equivalent to computing max flow of s to t.

// Hungarian
struct Hungarian{
    vvi G;
    vi bf;
    vi gf;
    int girl_size;
    vi vis;

    Hungarian( const vvi &_G, const int gs ): G( _G ), girl_size( gs ){
        bf.resize( girl_size );
        gf.resize( G.size(), -2 );
        vis.resize( girl_size );
        fill( bf.begin(), bf.end(), -1 );
    }

    bool foundMate( int u, const vvi &G ){
        for( int v : G[ u ] ){ // u: boy, v: girl
            if( vis[ v ] ) continue;
            vis[ v ] = 1;
            if( bf[ v ] == -1 || foundMate( bf[ v ], G ) ){
                bf[ v ] = u;
                gf[ u ] = v;
                return true;
            }
        }
        return false;
    }

    int maxMatch(){
        int res = 0;
        for( int i = 0; i < G.size(); ++i ){
            fill( vis.begin(), vis.end(), 0 );
            if( foundMate( i, G ) ) ++res;
        }
        return res;
    }
};

void solve(){
    int N, K; cin >> N >> K;
    vvi stock( N, vi( K ) );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < K; ++j )
            cin >> stock[ i ][ j ];
    vvi G( N );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < N; ++j ) if( i != j ){
            bool ng = false;
            for( int k = 0; k < K; ++k )
                if( not ( stock[ i ][ k ] < stock[ j ][ k ] ) )
                    ng = true;
            if( not ng ) G[ i ].push_back( j );
        }
    Hungarian hung( G, N );
    cout << N - hung.maxMatch() << "\n";
}

// Dinic
struct Dinic{
    int n, m, s, t;
    vector< Nedge > edge;
    vvi G;
    vb vis;
    vi dis;
    vi cur;
    Dinic( int sz ){
        n = sz;
        edge.clear();
        G.clear(); G.resize( sz );
        vis.clear(); vis.resize( sz );
        dis.clear(); dis.resize( sz );
        cur.clear(); cur.resize( sz );
    }
    void add_edge( int from, int to, int cap ){
        edge.push_back( Nedge( from, to, cap, 0 ) );
        edge.push_back( Nedge( to, from, 0, 0 ) );
        m = edge.size();
        G[ from ].push_back( m - 2 );
        G[ to ].push_back( m - 1 );
    }
    bool BFS(){
        fill( vis.begin(), vis.end(), 0 );
        queue< int > que;
        que.push( s );
        dis[ s ] = 0;
        vis[ s ] = 1;
        while( not que.empty() ){
            int x = que.front(); que.pop();
            for( int i = 0; i < G[ x ].size(); ++i ){
                Nedge &e = edge[ G[ x ][ i ] ];
                if( not vis[ e.to ] and e.cap > e.flow )
                    vis[ e.to ] = 1,
                    dis[ e.to ] = dis[ x ] + 1,
                    que.push( e.to );
            }
        }
        return vis[ t ];
    }
    int DFS( int x, int a ){
        if( x == t or a == 0 ) return a;
        int flow = 0, f;
        for( int &i = cur[ x ]; i < G[ x ].size(); ++i ){
            Nedge &e = edge[ G[ x ][ i ] ];
            if( dis[ x ] + 1 == dis[ e.to ] and ( f = DFS( e.to, min( a, e.cap - e.flow ) ) ) > 0 ){
                e.flow += f;
                edge[ G[ x ][ i ] ^ 1 ].flow -= f;
                flow += f;
                a -= f;
                if( a == 0 ) break;
            }
        }
        return flow;
    }
    int max_flow( int s, int t ){
        this->s = s; this->t = t;
        int flow = 0;
        while( BFS() )
            fill( cur.begin(), cur.end(), 0 ),
            flow += DFS( s, INF );
        return flow;
    }
};

void solve(){
    int N, K; cin >> N >> K;
    vvi stock( N, vi( K ) );
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < K; ++j )
            cin >> stock[ i ][ j ];
    Dinic *din = new Dinic( 2 * N + 2 );
    for( int i = 0; i < N; ++i )
        din->add_edge( 2 * N, i * 2, 1 ), // s = 2 * N
        din->add_edge( i * 2 + 1, 2 * N + 1, 1 ); // t = 2 * N + 1
    for( int i = 0; i < N; ++i )
        for( int j = 0; j < N; ++j ) if( i != j ){
            bool ng = false;
            for( int k = 0; k < K; ++k )
                if( not ( stock[ i ][ k ] < stock[ j ][ k ] ) )
                    ng = true;
            if( not ng ) din->add_edge( i * 2, j * 2 + 1, 1 );
        }
    cout << N - din->max_flow( 2 * N, 2 * N + 1 ) << "\n";
}