SRM 356 Div1 Medium MarriageProblemRevised

問題

複数の男女がいる。かれらのお互いの友好度がpreferencesとして与えられる。preferences[i][j]が'1'のとき男iと女jは結婚に適しており、'0'のときは適していない。一夫多妻型か多夫一妻型の結婚が認められている（多夫多妻制は不可）ときにすべての男女が夫婦に属するように結婚を組んだ場合の最小の夫婦数を求めよ。

やりかた

男女合わせてせいぜい24人以下なので全探索で十分。一夫か一妻となる人間を全列挙し、それらと夫婦になれる女（もしくは男）を全部を挙げていき、全部の人間がいずれかの夫婦に属していればそのパターンはOK。この場合、一夫もしくは一妻となる人間の数が結婚数になるのでこの数の最小値を求めればいい。

以下ソース。

class MarriageProblemRevised {  
public:
  int neededMarriages(vector <string> preferences) {
    int N = preferences.size(), M = preferences[0].size();
    int ans = INF;
    int a[24]; fill(a, a + 24, 0);
    for(int i = 0; i < N; i++){
      for(int j = 0; j < M; j++){
	if(preferences[i][j] == '1'){
	  a[i] |= (1 << (N + j));
	  a[j + N] |= (1 << i);
	}
      }
    }
    for(int i = 0; i < N + M; i++)//誰とも結婚できない孤立点があるなら-1
      if(a[i] == 0) return -1;

    for(int S = 0; S < 1 << (N + M); S++){
      int married = 0;
      for(int i = 0; i < N + M; i++){
	if(S >> i & 1){
	  married |= a[i];
	  married |= (1 << i);//便宜上自身とも結婚する
	}
      }
      if(married == (1 << (N + M)) - 1)//全員結婚した
	ans = min(ans, __builtin_popcount(S));
    }
    return ans >= N + M ? -1 : ans;
  }
};