HDU1528 Card Game Cheater 二分匹配最大点覆盖有关问题

HDU1528 Card Game Cheater 二分匹配最大点覆盖问题

这道题目还是比较简单的  就是建图有些问题

Adam和Eve打牌，Eve是能够可以看到Adam的牌，牌的顺序先看大小，如果大小一样，再看C，D，H（依次增大），每次出一张牌，大的算赢一次，求出Eve最多能赢多少次。

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long
#define LL __int64
#define eps 1e-8
const ll INF=9999999999999;

using namespace std;

#define M 400000100

#define inf 0xfffffff

//vector<pair<int,int> > G;
//typedef pair<int,int> P;
//vector<pair<int,int>> ::iterator iter;
//
//map<ll,int>mp;
//map<ll,int>::iterator p;

//vector<int>G[8000];

int mp[1212][1212];
int marry[1212];
bool vis[1212];
int dx[1212],dy[1212];

int dis[2][4]={0,-1,0,1,1,0,-1,0};

int n,m,k;

void clear()
{
	memset(marry,-1,sizeof(marry));
	memset(vis,false,sizeof(vis));
	memset(mp,0,sizeof(mp));/*
	for(int i=0;i<=m;i++)
		G[i].clear();*/
}

int find(char c)
{
	if(c=='C')
		return 1;
	if(c=='D')
		return 2;
	if(c=='S')
		return 3;
	if(c=='H')
		return 4;
	if(c=='T')
		return 10;
	if(c=='J')
		return 11;
	if(c=='Q')
		return 12;
	if(c=='K')
		return 13;
	if(c=='A')
		return 14;
	if(c>='2'&& c<='9')
		return c-'0';
}

bool dfs(int x)
{
	for(int i=0;i<n;i++)
	{
		if(mp[x][i] && !vis[i])
		{
			vis[i]=true;
			if(marry[i]==-1 || dfs(marry[i]))
			{
				marry[i]=x;
				return 1;
			}
		}
	}
	return 0;
}

int main(void)
{
	int t;
	cin>>t;
	while(t--)
	{
		clear();
		cin>>n;
		char c,s;
		int u,v;
		for(int i=0;i<n;i++)
		{
			cin>>c>>s;
			u=find(c);
			v=find(s);
			dx[i]=(u-1)*4+v;
		}
		for(int i=0;i<n;i++)
		{
			cin>>c>>s;
			u=find(c);
			v=find(s);
			dy[i]=(u-1)*4+v;
		}
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				if(dy[i]>dx[j])//这里按照题目要求来建图
					mp[i][j]=1;
		int ans=0;
		for(int i=0;i<n;i++)
		{
			memset(vis,false,sizeof(vis));
			if(dfs(i))
				ans++;
		}
		cout<<ans<<endl;
	}
}