purifying machine(二分图最大匹配,建图很重要).cpp

杭电acm解题报告2001---2099.

//二分图匹配按照1的个数的奇偶分为两部分
//如果某两个能一次处理掉连一条边，求出最大匹配，最后加上所有没被匹配的
#include<cstdio>
#include<string>
#include<vector>
#include<map>
using namespace std;

const int Max = 1100;
vector< vector<int> > Bmap;
int n, m;
int mark[Max];
bool flag[Max];
char in_ch[2][1200][12];
char in_t[12];
int num[2];
map<string , bool> hash;

bool dfs(int pos)
{
	int i, pre, tp;
	for(i=0; i < Bmap[pos].size() ;i++) {
		tp = Bmap[pos][i];
		if( !flag[tp] ) {
			flag[tp] = true;
			pre = mark[tp];
			mark[tp] = pos;
			if(pre==-1 || dfs(pre)) {
				return true;
			}
			mark[tp] = pre;
		}
	}
	return false;
}

inline int Max_Match()
{
	int mmax = 0, i;
	for(i=0; i < num[0] ;i++) {
		memset(flag,0,sizeof(flag));
		if( dfs(i) ) {
			mark[i] = i;
			mmax++;
		}
	}
	return mmax;
}

void make_Bi_Graph()
{
	int i,j,k;
	for(i=0; i<num[0] ;i++) {
		for(j=0; j<num[1] ;j++) {
			int dif = 0;
			for(k=0;k<n;k++) {
				if(in_ch[0][i][k] != in_ch[1][j][k]) {
					dif ++;
				}
			}//cal diffrence positions
			if(dif == 1) {//could both be solve
				Bmap[i].push_back(num[0] + j);
			}
		}
	}
}

int main()
{
	int i, j, k, t;

	while (scanf("%d %d", &n, &m) ==2) {
		if(n == 0 && m == 0) {
			break;
		}
		getchar();
		hash.clear();

		num[0] = num[1] = 0;
		for(i=0;i<m;i++) {
			gets(in_t);
			k = 0;
			int one = 0;
			int pos = -1;
			while (in_t[k]) {
				if(in_t[k] == '1') {
					one ++;
				}
				else if(in_t[k] == '*') {
					pos = k;
				}
				k ++;
			}//cal 1 and 0
			if(pos != -1) {
				in_t[pos] = '1';
				if(!hash[ string(in_t) ]) {
					strcpy(in_ch[(one+1)%2][ num[(one+1)%2] ], in_t);
					num[(one+1)%2] ++;
					hash[ string(in_t) ] = true;
				}
				in_t[pos] = '0';
			}
			if(!hash[ string(in_t) ]) {
				strcpy( in_ch[one%2][ num[one%2] ], in_t);
				num[one%2] ++;
				hash[ string(in_t) ] = true;
			}
		}
		
		Bmap.clear();
		Bmap.resize(num[0]+num[1]+10);
		memset(mark,-1,sizeof(mark));

		make_Bi_Graph();
		int ans = Max_Match();
		for(i=0; i<num[0]+num[1] ;i++) {
			if(mark[i] == -1) {//add unmatch cheese
				ans ++;
			}
		}
		printf("%d\n", ans);
	}
}