Brief description :

二分图完备匹配计数，所谓完备匹配是要求可以完全覆盖一边的点。

#include 
using namespace std;
const int N = 20, S = 1 << 20;
bool G[N][N];
int F[2][S], n, m, p, q, up, ans;

void init(){
	memset(G, false, sizeof(G));
	int t, y;
	for (int x=0;x> t;
		for (int i=0;i> y; y--;
			G[x][y] = true;
		}
	}
	up = 1 << m;
}


void solve(){
	memset(F, 0, sizeof(F));
	F[p = 0][0] = 1;
	for (int i=0;i> n >> m){
		init(); solve();
		cout << ans << endl;
	}
}




// PKU 2441 Arrange the Bulls

#include 
using namespace std;
const int N = 20, S = 1 << 20;
bool G[N+1][N]; int n, m;
int s, d, ans;


struct hashTable {
	int state[S], pos[S], sz;
	int key[S];
	
	inline void clear() {
		sz = 0; 
		memset(pos, -1, sizeof(pos));
	}
	inline void insert(int s) {
		//cout << s << " " << d << endl;
		if (pos[s]!= -1) {
			key[pos[s]] += d;
			return;
		}
		state[sz] = s, key[sz] = d;
		pos[s] = sz++;
	}
	inline int search(int s) {
		if (pos[s]!=-1) return key[pos[s]];
		return 0;
	}
} H[2] , *src , *des;




void init(){
	memset(G, false, sizeof(G));
	int t, y;
	for (int x=1;x<=n;x++){
		cin >> t;
		for (int i=0;i> y; y--;
			G[x][y] = true;
		}
	}
}


void solve(){
	src = H, des = src + 1, d = 1;
	des->clear(), des->insert(0);

	
	for (int i=1;i<=n-1;i++){
		swap(src, des), des->clear();
		for (int ii=0;iisz;ii++){
			s = src->state[ii], d = src->key[ii];
			for (int j=0;jinsert(s|1<sz;ii++){
		s = des->state[ii], d = des->key[ii];
		for (int j=0;j> n >> m){
		init(); solve();
		cout << ans << endl;
	}
}

External link :

http://poj.org/problem?id=2441

Posted by xiaodao
Category: 日常