题意与分析
题意是这样的:有\(n\)张牌,然后第一行是Adam的牌,第二行是Eve的牌:每两个字符代表一张牌,第一个字符表示牌的点数,第二个表示牌的花色。Adam和Eve每次从自己的牌中选出一张牌进行比较,先看大小再看花色,花色顺序是C,D,S,H(依次增大),谁的牌大谁就加一分,问Eve最多能得到多少分。
思路:最大二分匹配,Eve的牌为集合1,Adam的牌为集合2,集合1中的牌与集合2中比它小的牌建立联系,找最大匹配。这种两个集合的要想到试试二分图。
代码
/* ACM Code written by Sam X or his teammates.
* Filename: hdu1528.cpp
* Date: 2018-11-18
*/
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define PB emplace_back
#define MP make_pair
#define fi first
#define se second
#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)
#define per(i,a,b) for(repType i=(a); i>=(b); --i)
#define ZERO(x) memset(x, 0, sizeof(x))
#define MS(x,y) memset(x, y, sizeof(x))
#define ALL(x) (x).begin(), (x).end()
#define QUICKIO \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
using namespace std;
using pi=pair<int,int>;
using repType=int;
using ll=long long;
using ld=long double;
using ull=unsigned long long;
vector<pair<int,int> > A,E;
inline int clr(char ch)
{
switch(ch)
{
case 'C': return 1;
case 'D': return 2;
case 'S': return 3;
case 'H': return 4;
}
}
inline int id(char ch)
{
if(ch>='0' && ch<='9') return ch-'0';
switch(ch)
{
case 'T': return 10;
case 'J': return 11;
case 'Q': return 12;
case 'K': return 13;
case 'A': return 14;
}
}
const int MAXN=30;
int G[MAXN][MAXN];
bool used[MAXN];
int linker[MAXN],k;
int dfs(int u)
{
rep(v,0,k-1)
{
if(G[u][v] && !used[v])
{
used[v]=true;
if(linker[v]==-1 || dfs(linker[v]))
{
linker[v]=u;
return true;
}
}
}
return false;
}
int hungary()
{
int res=0;
MS(linker,-1);
rep(i,0,k-1)
{
ZERO(used);
if(dfs(i)) res++;
}
return res;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
ZERO(G);
A.clear();
E.clear();
scanf("%d", &k);
rep(i,1,k)
{
getchar();
char chi,chc;
scanf("%c%c", &chi, &chc);
A.PB(id(chi),clr(chc));
}
rep(i,1,k)
{
getchar();
char chi,chc;
scanf("%c%c", &chi, &chc);
E.PB(id(chi),clr(chc));
}
rep(i,0,k-1)
{
rep(j,0,k-1)
{
if(E[i]>A[j])
G[i][j]=true;
}
}
printf("%d\n", hungary());
}
return 0;
}