nyoj 1037 Postscript of Tian Ji racing

本文主要是介绍nyoj 1037 Postscript of Tian Ji racing，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

   一道卡贪心的题。

也算一道改编题。

此题的解法推荐为二分图的最大匹配。

首先将输入数据转换一下，然后将满足题意的一组牌建立条边，最终边的覆盖数即为 LN 最后可得的分数。

然后求出最大匹配即可。

代码如下：

 
#include<stdio.h>
#include<string.h>
char card[30][5];
char s[5];
int map[30][30];
int vis[30];
int link[30];
int k;
int find(int a)
{for(int i=1; i<=k; i++){if(!vis[i]&&map[a][i]){vis[i]=1;if(link[i]==-1||find(link[i])){link[i]=a;return 1;}}}return 0;
}
int sum()
{int res=0;memset(link,-1,sizeof(link));for(int i=1; i<=k; i++){memset(vis,0,sizeof(vis));if(find(i))res++;}return res;
}
void change(char a[])
{if(a[0]=='A')a[0]='0'+14;else if(a[0]=='T')a[0]='0'+10;else if(a[0]=='J')a[0]='0'+11;else if(a[0]=='Q')a[0]='0'+12;else if(a[0]=='K')a[0]='0'+13;if(a[1]=='H')a[1]='4';else if(a[1]=='S')a[1]='3';else if(a[1]=='D')a[1]='2';else if(a[1]=='C')a[1]='1';
}
int main()
{//freopen("a.txt","r",stdin);//freopen("out.txt","w",stdout);int t;scanf("%d",&t);while(t--){memset(map,0,sizeof(map));memset(card,'\0',sizeof(card));scanf("%d",&k);for(int i=1; i<=k; i++)scanf("%*c%s",card[i]);//printf("**\n");for(int i=1; i<=k; i++){scanf("%*c%s",s);for(int j=1; j<=k; j++){change(card[j]);change(s);if(s[0]>card[j][0])map[i][j]=1;else if(s[0]==card[j][0]&&s[1]>card[j][1])map[i][j]=1;//printf("**%d\n",map[i][j]);}}int res=sum();printf("%d\n",res);}return 0;
}

这篇关于nyoj 1037 Postscript of Tian Ji racing的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---