SRM 356 550pt : MarriageProblemRevised

keyword

最小支配集合　C++

問題概要

ノード数12+12以下の2部グラフが与えられる。最小支配集合を求める問題。ただし孤立点がある場合を除く。

解法

各ノードに対して、そのノードが支配するノードをビットで持っておく。後は2^24通り全探索するだけ。2部グラフであることは特に使わない。

#include <cstring>
#include <vector>
#include <string>
using namespace std;

const int MAX_V = 30;
int V;

int G[MAX_V];

struct MarriageProblemRevised {

	int neededMarriages(vector <string> preferences) {
		V = preferences.size();
		for(int i=0; i<V; i++){
			for(int j=0; j<(int)preferences[i].size(); j++)if(preferences[i][j]=='1'){
				add_edge(i, j+V);
			}
		}
		V += preferences[0].size();
		for(int i=0; i<V; i++){
			G[i] |= 1<<i;
		}

		for(int i=0; i<V; i++)if(__builtin_popcount(G[i])==1){
			return -1;
		}

		int ret = 1<<29;
		for(int bit=0; bit<(1<<V); bit++)if(__builtin_popcount(bit) < min(ret,13)){
			int t = 0;
			for(int i=0; i<V; i++)if((bit>>i)&1){
				t |= G[i];
			}
			if(__builtin_popcount(t) == V){
				ret = __builtin_popcount(bit);
			}
		}
		return ret==1<<29?-1:ret;
	}

	void add_edge(int u, int v){
		G[v] |= 1<<u;
		G[u] |= 1<<v;
	}

};