1027 姓名与ID[二分图匹配(匈牙利)]
题目描述 Description
有N个人，各自有一个姓名和ID（别名）。每个人的姓名和ID都没有重复。这些人依次进入一间房间，然后可能会离开。过程中可以得到一些信息，告知在房间里的某个人的ID。你的任务是准确地确定每个人的ID。
输入描述 Input Description
第一行是整数N，表示N个人，N<=20。
接下来的一行是N个人的ID，用一个空格分隔。
接下来的若干行是过程的记录：一个字母和一个字符串。字母是E、L或M中的一个。E表示进入房间，后面跟的字符串表示进来的人的姓名；L表示离开房间，后面跟的字符串表示离开的人的姓名；M表示回答询问，后面跟的字符串表示：当前用这个ID人在房间里面。
最后一行Q表示结束。
所有的姓名和ID都由不超过20个的小写字母组成。所有姓名都会在记录中出现。
一开始时，房间时空的。
输出描述 Output Description
共N行，每行形如：“姓名:ID”，如果ID不能确定，输出???。
按照姓名的字典顺序输出。
样例输入 Sample Input
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
样例输出 Sample Output
bonnie:fatman
booth:???
clyde:frenchie
knuckles:bigman
moriarty:???
mugsy:mangler
ugati:sinbad
数据范围及提示 Data Size & Hint
分类标签 Tags 点此展开
AC代码：
#include<bits/stdc++.h> using namespace std; bool e[25][25]; int clock_vis,n,flag[25],vis[25],in[25],match[25]; string P[25],Q[25];//字符串数组 map<string,int>name; map<string,int>id; bool find(int u){//二分图匹配 for(int i=1;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 1; } } } return 0; } bool check(int u){//检查 if(flag[u]) return 0; flag[u]=1; for(int i=1;i<=n;i++){ if(!vis[i]&&e[u][i]&&match[i]!=u){//当前没配的&&可以配&&i原配不是u vis[i]=1; if(!match[i]||!check(match[i])) return 0;//换一个配方案可行 } } return 1; } int main(){ memset(e,1,sizeof(e)); cin>>n; for(int i=1;i<=n;i++){ string s; cin>>s; id[s]=i; Q[i]=s; } for(int l=0;;){ char w; string s; cin>>w>>s; if(w=='Q') break; if(w=='E'){ if(name.count(s)==0)//没出现过 P[l]=s,name[s]=++l;//个数+1 in[name[s]]=1; } if(w=='L') in[name[s]]=0; if(w=='M') for(int i=1;i<=n;i++) if(!in[i]) e[i][id[s]]=0;//如果不在就没边 } sort(P,P+n);//直接字符串排序 for(int i=1;i<=n;i++) clock_vis=i,find(i); for(int i=0;i<n;i++){ memset(flag,0,sizeof(flag)); memset(vis,0,sizeof(vis)); cout<<P[i]<<":"; if(check(name[P[i]])){ for(int j=1;j<=n;j++) if(match[j]==name[P[i]]) cout<<Q[j]<<endl; } else cout<<"???"<<endl; } return 0; }