本文主要是介绍HDU 1179，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 1179
题意：
单独翻译，英语较弱的就是很吃力（比如 me）！
一些人去买魔法棒，反转的就是魔法棒选择跟着谁，你是店主，肯定想卖出最多的魔棒，
回到了二分图的最大匹配问题。
键入数据提示：
（多组测试数据）
顾客的数目 N ，魔法棒数目 M；
接下来 M 行， 第 j 行的第一个数字是魔法棒中意的人数个数 K，依次是顾客编号。
思路：
二分图最大匹配的模板。
ac code1容器 vector 实现：
1508 KB 15 ms
#include<stdio.h>
#include<cstring>
#include<vector>
using namespace std;
const int MYDD=1103;
const int MAXN=128;int Magic[MAXN];
bool vis[MAXN]; //魔法棒销售状态
vector<int> Matching[MAXN];//建立容器
bool HK(int magic,int n) {for(int j=0; j<Matching[magic].size(); j++) {//遍历魔法棒中意的顾客 int v=Matching[magic][j];if(!vis[v]) {vis[v]=true;if(Magic[v]==-1||HK(Magic[v],n)) {Magic[v]=magic;//当前 magic 魔法棒卖给的顾客 magic[j]return true;}}}return false;
}int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF) {for(int j=0; j<=m; j++)Matching[j].clear();for(int j=1; j<=m; j++) {int k;scanf("%d",&k);while(k--) {int t;scanf("%d",&t);Matching[j].push_back(t);}}int ans=0;memset(Magic,-1,sizeof(Magic));for(int j=1; j<=m; j++) {//遍历魔法棒 memset(vis,false,sizeof(vis));if(HK(j,n)) ans++;}printf("%d\n",ans);}return 0;
}
ac code2二维数组实现：
1472KB 0ms
#include<stdio.h>
#include<cstring>
const int MYDD=1103;
const int MAXN=128;int Magic[MAXN];
bool vis[MAXN]; //魔法棒销售状态
int Matching[MAXN][MAXN]; //Matching
bool HK(int magic,int customer) {for(int j=1; j<=customer; j++) {if(!vis[j]&&Matching[magic][j]) {vis[j]=true;if(Magic[j]==-1||HK(Magic[j],customer)) {Magic[j]=magic;//当前 magic 魔法棒卖给的顾客 magic[j]return true;}}}return false;
}int main() {int n,m;while(scanf("%d%d",&n,&m)!=EOF) {memset(Matching,0,sizeof(Matching));for(int j=1; j<=m; j++) {int k;scanf("%d",&k);while(k--) {int t;scanf("%d",&t);Matching[j][t]=1;}}int ans=0;memset(Magic,-1,sizeof(Magic));for(int j=1; j<=m; j++) {memset(vis,false,sizeof(vis));if(HK(j,n)) ans++;}printf("%d\n",ans);}return 0;
}
这篇关于HDU 1179的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
