card game cheater(最大二分匹配).cpp

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

#include<cstdio>
#include<memory>
#include<vector>
using namespace std;

const int Max = 60;
vector< vector<int> > Bmap;
int n, m, k, nm;
int mark[Max];
bool flag[Max];
struct node {
	int s,v;
	bool operator < (const node & t) const {
		if (v != t.v) {
			return v < t.v;
		}
		return s < t.s;
	}
	void get_value(char card[]) {
		char ch = card[0];
		switch(ch) {
		case 'T':
			v = 10;
			break;
		case 'J':
			v = 11;
			break;
		case 'Q':
			v = 12;
			break;
		case 'K':
			v = 13;
			break;
		case 'A':
			v = 14;
			break;
		default:
			v = ch - '2' +2;
		}
		ch = card[1];
		switch(ch) {
		case 'H':
			s = 4;
			break;
		case 'S':
			s = 3;
			break;
		case 'D':
			s = 2;
			break;
		case 'C':
			s = 1;
			break;
		}
	}
}cs[Max];

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 < n ;i++) {
		memset(flag,0,sizeof(flag));
		if( dfs(i+n) ) {
			mmax++;
		}
	}
	return mmax;
}

int main()
{
	int i, j, id1, id2, t;
	char card[5];
	scanf("%d", &t);
	while(t --) {
		scanf("%d", &n);
		Bmap.clear();
		Bmap.resize(2*n+10);
		memset(mark,-1,sizeof(mark));
		getchar();
		for(i=0; i < n ;i++) {
			scanf("%s", card);
			cs[i].get_value(card);
		}
		getchar();
		for(i=0; i < n ;i++) {
			scanf("%s", card);
			cs[n+i].get_value(card);
			for (j=0; j < n ;j++) {
				if (cs[j] < cs[n+i]) {
					Bmap[n+i].push_back(j);
				}
			}
		}
		printf("%d\n", Max_Match());
	}
}