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