hdu1528匈牙利算法---邻接矩阵

左手的ㄟ右手 2022-01-17 04:13 230阅读 0赞

赤裸裸的二分匹配。。。注意处理好输入

\#include<cstdlib>  
\#include<iostream>  
\#include<cstring>

using namespace std;

int mj\[28\]\[28\];  
int flag\[28\];  
int result\[28\];  
int n;

bool Find(int x)  
\{  
int j;  
for(j=1;j<=n;j++)  
\{  
if(mj\[x\]\[j\]!=0&&flag\[j\]==0)  
\{  
flag\[j\]=1;  
if(result\[j\]==0||Find(result\[j\]))  
\{  
result\[j\]=x;  
return true;  
\}  
\}  
\}  
return false;  
\}

int main()  
\{  
int t,i,j,ans,x1\[28\],x2\[28\],y1\[28\],y2\[28\];  
char ch\[4\];  
scanf("%d",&t);  
while(t--)  
\{  
scanf("%d",&n);  
memset(mj,0,sizeof(mj));  
memset(result,0,sizeof(result));  
for(i=1;i<=n;i++)  
\{  
scanf("%s",ch);  
if(ch\[0\]=='A') x1\[i\]=14;  
else if(ch\[0\]=='K') x1\[i\]=13;  
else if(ch\[0\]=='Q') x1\[i\]=12;  
else if(ch\[0\]=='J') x1\[i\]=11;  
else if(ch\[0\]=='T') x1\[i\]=10;  
else x1\[i\]=ch\[0\]-'0';

if(ch\[1\]=='H') y1\[i\]=4;  
else if(ch\[1\]=='S') y1\[i\]=3;  
else if(ch\[1\]=='D') y1\[i\]=2;  
else y1\[i\]=1;  
\}  
for(i=1;i<=n;i++)  
\{  
scanf("%s",ch);  
if(ch\[0\]=='A') x2\[i\]=14;  
else if(ch\[0\]=='K') x2\[i\]=13;  
else if(ch\[0\]=='Q') x2\[i\]=12;  
else if(ch\[0\]=='J') x2\[i\]=11;  
else if(ch\[0\]=='T') x2\[i\]=10;  
else x2\[i\]=ch\[0\]-'0';

if(ch\[1\]=='H') y2\[i\]=4;  
else if(ch\[1\]=='S') y2\[i\]=3;  
else if(ch\[1\]=='D') y2\[i\]=2;  
else y2\[i\]=1;  
\}  
ans=0;  
for(i=1;i<=n;i++)  
\{  
for(j=1;j<=n;j++)  
\{  
if(x2\[i\]>x1\[j\]||(x2\[i\]==x1\[j\]&&y2\[i\]>y1\[j\]))  
mj\[i\]\[j\]=1;  
\}  
\}  
for(i=1;i<=n;i++)  
\{  
memset(flag,0,sizeof(flag));  
if(Find(i)) ans++;  
\}  
printf("%d\\n",ans);

\}  
return 0;  
\}

转载于:https://blog.51cto.com/8590696/1358868

发表评论取消回复

表情：

评论列表（有 0 条评论，230人围观）

还没有评论，来说两句吧...

相关阅读

相关匈牙利算法

匈牙利算法：月老准备给n个女孩与n个男孩牵红线，成就一对对美好的姻缘。现在，由于一些原因，部分男孩与女孩可能结成幸福的一家，部分可能不会结成幸福的家庭。现在已知

桃扇骨/ 2022年10月01日 00:51/ 0 赞/ 146 阅读

相关 HDU 1150 Machine Schedule（二分匹配+匈牙利算法）

As we all know, machine scheduling is a very classical problem in computer science and h

深藏阁楼爱情的钟/ 2022年06月10日 05:18/ 0 赞/ 153 阅读

相关 HDU 1528 Card Game Cheater（二分图匹配+匈牙利算法+模拟）

Problem Description Adam and Eve play a card game using a regular deck of 52 cards. The

水深无声/ 2022年06月10日 02:55/ 0 赞/ 198 阅读

相关 HDU 1082 COURSES （二分图匹配之匈牙利算法）

Consider a group of N students and P courses. Each student visits zero, one or more than

秒速五厘米/ 2022年06月10日 00:47/ 0 赞/ 199 阅读

相关 HDU 3549 Flow Problem（最大流+EK邻接表||邻接矩阵||dinic算法模板比较）

Network flow is a well-known difficult problem for ACMers. Given a graph, your task is t

柔光的暖阳◎/ 2022年06月09日 11:16/ 0 赞/ 186 阅读

相关【二分图匹配-匈牙利算法】Courses HDU - 1083

Think: 1知识点：二分图匹配-匈牙利算法 2题意：T组测试数据，每组测试数据输入n, m表示n门课程，m名学生，询问是否存在n名学生，使得他们满足每名学生学习了至

矫情吗；*/ 2022年06月09日 10:58/ 0 赞/ 215 阅读

相关邻接矩阵

题目描叙：无向图的表示方法邻接矩阵，需打印到屏幕。有权。分析：邻接矩阵的核心思想便是顶点表和边表。我们可以定义一个结构体，里面包含一个顶点表（即一个vexs

傷城~/ 2022年04月23日 01:02/ 0 赞/ 188 阅读

相关匈牙利算法

匈牙利算法就是匹配最大度的问题 max_node =100 bigraph=[[ False for i in range(max_node)]for

约定不等于承诺〃/ 2022年04月22日 07:22/ 0 赞/ 174 阅读

相关 hdu1528匈牙利算法---邻接矩阵

赤裸裸的二分匹配。。。注意处理好输入 \include<cstdlib> \include<iostream> \include<cstring> using

左手的ㄟ右手/ 2022年01月17日 04:13/ 0 赞/ 231 阅读

相关邻接矩阵

//无向网的建立（采用邻接矩阵） include<iostream> using namespace std; const int

傷城~/ 2021年12月16日 06:25/ 0 赞/ 384 阅读