POJ 3866 Exclusive Access 2 ( Dilworth Theorem, DP, bitmask )

3866 -- Exclusive Access 2

N ≤ 100

TL: 5000 ms
ML: 65536 KB

```#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
#include <cassert>
#include <cstring>
#include <string>
using namespace std;

template< class T1, class T2 >
int upmin( T1 &x, T2 v ){
if( x <= v ) return 0;
x = v;
return 1;
}

const int MAXNODE = 15;

int N;
vector< pair< string, string > > edge;
map< string, int > name2id;
string id2name[ MAXNODE ];
int id_size;
bool bi_edge[ MAXNODE ][ MAXNODE ];
int has_edge[ 1 << MAXNODE ];
int dp[ 1 << MAXNODE ]; // minimum antichain size
int dc[ 1 << MAXNODE ]; // previous optimal decision
vector< int > antichain;
int id_antichain[ MAXNODE ];

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
edge = vector< pair< string, string > >( N );
for( int i = 0; i < N; ++i ){
cin >> edge[ i ].first >> edge[ i ].second;
}
for( int i = 0; i < N; ++i ){
if( not name2id.count( edge[ i ].first ) ){
int f = name2id.size();
name2id[ edge[ i ].first ] = f;
id2name[ name2id[ edge[ i ].first ] ] = edge[ i ].first;
}
if( not name2id.count( edge[ i ].second ) ){
int f = name2id.size();
name2id[ edge[ i ].second ] = f;
id2name[ name2id[ edge[ i ].second ] ] = edge[ i ].second;
}
}
id_size = name2id.size();
for( int i = 0; i < N; ++i ){
bi_edge[ name2id[ edge[ i ].first ] ][ name2id[ edge[ i ].second ] ] = 1;
bi_edge[ name2id[ edge[ i ].second ] ][ name2id[ edge[ i ].first ] ] = 1;
}
for( int s = 0; s < 1 << id_size; ++s ){
for( int i = 0; i < id_size; ++i ){
if( s >> i & 1 ) continue;
int he = 0;
for( int j = 0; j < id_size; ++j ){
if( ~s >> j & 1 ) continue;
he |= bi_edge[ i ][ j ];
}
has_edge[ s | 1 << i ] = has_edge[ s ] | he;
}
}
memset( dp, 0x3f3f3f3f, sizeof( dp ) );
dp[ 0 ] = 0;
for( int s = 1; s < 1 << id_size; ++s ){
for( int subs = s; subs; subs = ( subs - 1 ) & s ){
if( has_edge[ subs ] ) continue;
if( upmin( dp[ s ], dp[ s - subs ] + 1 ) ){
dc[ s ] = subs;
}
}
}
cout << dp[ ( 1 << id_size ) - 1 ] - 2 << endl;
vector< int > antichain;
for( int u = ( 1 << id_size ) - 1; u; u -= dc[ u ] ){
antichain.push_back( dc[ u ] );
}
for( int i = 0; i < antichain.size(); ++i ){
for( int j = 0; j < id_size; ++j ){
if( antichain[ i ] >> j & 1 ){
id_antichain[ j ] = i;
}
}
}
for( int i = 0; i < N; ++i ){
int x = id_antichain[ name2id[ edge[ i ].first ] ];
int y = id_antichain[ name2id[ edge[ i ].second ] ];
assert( x != y );
if( not ( x < y ) ) swap( edge[ i ].first, edge[ i ].second );
cout << edge[ i ].first << " " << edge[ i ].second << endl;
}
return 0;
}
```