HDOJ1528、1962解题报告【二分图】

题目地址：

　　http://acm.hdu.edu.cn/showproblem.php?pid=1528

　　http://acm.hdu.edu.cn/showproblem.php?pid=1962

　　（这两题为同样的题面）

题目概述：

　　给你两副牌，请你变动第二幅的顺序，使得对应位置上第二副牌的胜利场数最多。

　　两张牌比较时，先比较数字大小，A最大，2最小，如果数字相同就比较花色，红桃>黑桃>方片>梅花。

大致思路：

　　对于第二副牌中的第i张牌，枚举第一副牌，如果第二i张牌比第一副牌中的第j张牌大，就在二图中连一条i-j之间的无向边，答案就是所建立的二分图的最大匹配。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <vector>
  6 #include <ctime>
  7 #include <map>
  8 #include <queue>
  9 #include <cstring>
 10 #include <algorithm>
 11 using namespace std;
 12 
 13 #define sacnf scanf
 14 #define scnaf scanf
 15 #define maxn 65
 16 #define maxm 26
 17 #define inf 1061109567
 18 #define Eps 0.00001
 19 const double PI=acos(-1.0);
 20 #define mod 7
 21 #define MAXNUM 10000
 22 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
 23 double Abs(double x) {return (x<0)?-x:x;}
 24 typedef long long ll;
 25 typedef unsigned int uint;
 26 
 27 char a[maxn][2];
 28 char c[maxn*2];int k;
 29 int G[maxn][maxn];
 30 int vis[maxn],l[maxn];
 31 
 32 bool compare(char x,char y,int pos)
 33 {
 34     return (x==a[pos][0])?c[(int)y]>c[(int)a[pos][1]]:c[(int)x]>c[(int)a[pos][0]];
 35 }
 36 
 37 bool dfs(int u)
 38 {
 39     for(int i=1;i<=k*2;i++)
 40     {
 41         if(!G[u][i]) continue;
 42         if(!vis[i])
 43         {
 44             vis[i]=1;
 45             if(l[i]==-1||dfs(l[i]))
 46             {
 47                 l[i]=u;
 48                 return true;
 49             }
 50         }
 51     }
 52     return false;
 53 }
 54 
 55 int hungary()
 56 {
 57     memset(l,-1,sizeof(l));
 58     int cnt=0;
 59     for(int i=1;i<=k;i++)
 60     {
 61         memset(vis,0,sizeof(vis));
 62         if(dfs(i)) cnt++;
 63     }
 64     return cnt;
 65 }
 66 
 67 int main()
 68 {
 69     //freopen("data.in","r",stdin);
 70     //freopen("data.out","w",stdout);
 71     //clock_t st=clock();
 72     int T;scanf("%d",&T);
 73     for(int i=2;i<=9;i++) c['0'+i]=i-1;
 74     c['T']=9;c['J']=10;c['Q']=11;c['K']=12;c['A']=13;
 75     c['C']=1;c['D']=2;c['S']=3;c['H']=4;
 76     while(T--)
 77     {
 78         scanf("%d",&k);
 79         for(int i=1;i<=2*k;i++)
 80         {
 81             for(int j=1;j<=2*k;j++) G[i][j]=0;
 82             if(i<=k) {getchar();scanf("%c%c",&a[i][0],&a[i][1]);}
 83         }
 84         char x,y;
 85         for(int i=1;i<=k;i++)
 86         {
 87             getchar();
 88             scanf("%c%c",&x,&y);
 89             for(int j=1;j<=k;j++)
 90                 if(compare(x,y,j))
 91                 {
 92                     G[i][k+j]=G[k+j][i]=1;
 93                 }
 94         }
 95         int ans=hungary();
 96         printf("%d
",ans);
 97     }
 98     //clock_t ed=clock();
 99     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
100     return 0;
101 }