1027 姓名与ID[二分图匹配(匈牙利)]
有N个人,各自有一个姓名和ID(别名)。每个人的姓名和ID都没有重复。这些人依次进入一间房间,然后可能会离开。过程中可以得到一些信息,告知在房间里的某个人的ID。你的任务是准确地确定每个人的ID。
第一行是整数N,表示N个人,N<=20。
接下来的一行是N个人的ID,用一个空格分隔。
接下来的若干行是过程的记录:一个字母和一个字符串。字母是E、L或M中的一个。E表示进入房间,后面跟的字符串表示进来的人的姓名;L表示离开房间,后面跟的字符串表示离开的人的姓名;M表示回答询问,后面跟的字符串表示:当前用这个ID人在房间里面。
最后一行Q表示结束。
所有的姓名和ID都由不超过20个的小写字母组成。所有姓名都会在记录中出现。
一开始时,房间时空的。
共N行,每行形如:“姓名:ID”,如果ID不能确定,输出???。
按照姓名的字典顺序输出。
7
bigman mangler sinbad fatman bigcheese frenchie capodicapo
E mugsy
E knuckles
M bigman
M mangler
L mugsy
E clyde
E bonnie
M bigman
M fatman
M frenchie
L clyde
M fatman
E ugati
M sinbad
E moriarty
E booth
Q
bonnie:fatman
booth:???
clyde:frenchie
knuckles:bigman
moriarty:???
mugsy:mangler
ugati:sinbad
分类标签 Tags 点此展开
第一行是整数N,表示N个人,N<=20。
接下来的一行是N个人的ID,用一个空格分隔。
接下来的若干行是过程的记录:一个字母和一个字符串。字母是E、L或M中的一个。E表示进入房间,后面跟的字符串表示进来的人的姓名;L表示离开房间,后面跟的字符串表示离开的人的姓名;M表示回答询问,后面跟的字符串表示:当前用这个ID人在房间里面。
最后一行Q表示结束。
所有的姓名和ID都由不超过20个的小写字母组成。所有姓名都会在记录中出现。
一开始时,房间时空的。
注意字母后跟的是什么!!!
E进入后标记,M后的id在房间,那么这个人就可能用这个ID(多连点没关系,但一定要对)
答案是这个人肯定配这个ID(不配这个Id就没的配了)
AC代码:
#include<bits/stdc++.h>
using namespace std;
bool e[][];
int clock_vis,n,flag[],vis[],in[],match[];
string P[],Q[];//字符串数组
map<string,int>name;
map<string,int>id;
bool find(int u){//二分图匹配
for(int i=;i<=n;i++){
if(vis[i]!=clock_vis&&e[u][i]){
vis[i]=clock_vis;
if(!match[i]||find(match[i])){
match[i]=u;
return ;
}
}
}
return ;
}
bool check(int u){//检查
if(flag[u]) return ;
flag[u]=;
for(int i=;i<=n;i++){
if(!vis[i]&&e[u][i]&&match[i]!=u){//当前没配的&&可以配&&i原配不是u
vis[i]=;
if(!match[i]||!check(match[i]))
return ;//换一个配方案可行
}
}
return ;
}
int main(){
memset(e,,sizeof(e));
cin>>n;
for(int i=;i<=n;i++){
string s;
cin>>s;
id[s]=i;
Q[i]=s;
}
for(int l=;;){
char w; string s;
cin>>w>>s;
if(w=='Q') break;
if(w=='E'){
if(name.count(s)==)//没出现过
P[l]=s,name[s]=++l;//个数+1
in[name[s]]=;
}
if(w=='L') in[name[s]]=;
if(w=='M')
for(int i=;i<=n;i++)
if(!in[i]) e[i][id[s]]=;//如果不在就没边
}
sort(P,P+n);//直接字符串排序
for(int i=;i<=n;i++)
clock_vis=i,find(i);
for(int i=;i<n;i++){
memset(flag,,sizeof(flag));
memset(vis,,sizeof(vis));
cout<<P[i]<<":";
if(check(name[P[i]])){
for(int j=;j<=n;j++)
if(match[j]==name[P[i]]) cout<<Q[j]<<endl;
}
else cout<<"???"<<endl;
}
return ;
}
最新文章
- windows 下使用Nginx替代apache作为服务器
- Linux DHCP通过OPTION43为H3C的AP下发AC地址
- ubuntu安装python一些安装包
- C 宏定义 理解(1)
- WordPaster-Firefox浏览器控件安装方法
- Radio Basics for RFID
- 函数调用导致堆栈不对称。原因可能是托管的 PInvoke 签名与非托管的目标签名不匹配。
- sqlserver提高篇续集
- 【转】NOR Flash擦写和原理分析
- VisualSVN服务器的本地搭建和使用
- Diagnostic Trouble Code诊断故障码
- 如何把checkbox做成radio一样的单选效果
- c# 继承与多种状态
- XSSExcelUtil
- H5开发APP考题和答案
- 【Struts2】剖析Struts2中的反射技术 ValueStack(值栈)
- vi和vim的三种模式
- WPF添加样式字典Style
- Peter Norvig:学习在于挑战和重复
- poj_1988 并查集
热门文章
- Hadoop on Mac with IntelliJ IDEA - 9 解决Type mismatch in value from map问题
- 汽车常用的ECU芯片
- 编写一个JavaScript函数 parseQueryString,把URL参数解析为一个对象
- 【转】python代码风格-PEP8
- Linux基础教程之/dev/null和/dev/zero的区别及其用法
- 关于form.submit()不能提交表单的错误原因
- jQuery.FlexiGrid使用总结
- BZOJ 1045: [HAOI2008] 糖果传递 数学
- BZOJ 1083: [SCOI2005]繁忙的都市 kruskal
- 几种Java写webservice的比较