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

3866 -- Exclusive Access 2

題意：
給一個 N 個無向邊的圖。求一種方案使所有邊定向，並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。

資料規模：
N ≤ 100
節點為 [ L, Z ] 間的大寫英文字母，數量不超過 15。
TL: 5000 ms
ML: 65536 KB

解法：
根據 Dilworth Theorem，可以知道，對於一個 DAG，最長路徑會是反鏈的最少划分數量。反鏈的定義為一個任兩元素都無法從一方到達另一方的集合，亦等價任意兩點不存在邊的集合。因此考慮用位元 dp 計算最少划分數量。

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