本文主要是介绍codevs1027 姓名与id，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求最大匹配后，判断每个人是否可以有别的匹配，沿原匹配走出回路则有。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
int n;
int line[30][30];
int b[30],g[30];
bool used[30];
map<string,int>name;
string na[30];
map<string,int>id;
string di[30];
set<int>se;
set<int>leave;
bool vis[30];
struct Node
{string name,id;bool operator<(const Node& u)const{return name<u.name;}
};
Node p[30];
int e=0;bool find(int x);
bool check(int x);
int main()
{memset(b,0,sizeof(b));memset(g,0,sizeof(g));string str;char ch[2];scanf("%d",&n);for(int i=0;i<n;i++){cin>>str;id[str]=i+1;di[i+1]=str;leave.insert(i+1);}int o=1;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)line[i][j]=1;}while(~scanf("%s",ch)){if(ch[0]=='Q')break;cin>>str;if(ch[0]=='E'){if(name[str]==0){name[str]=o++;na[o-1]=str;}se.insert(name[str]);leave.erase(name[str]);}else if(ch[0]=='L'){leave.insert(name[str]);se.erase(name[str]);}else{int k=id[str];for(set<int>::iterator it=leave.begin();it!=leave.end();it++){line[*it][k]=0;}}}for(int i=1;i<=n;i++){memset(used,0,sizeof(used));find(i);}for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));memset(used,0,sizeof(used));if(check(i)){p[e].name=na[i];p[e++].id="???";}else{p[e].name=na[i];p[e].id=di[b[i]];e++;}}sort(p,p+e);for(int i=0;i<e;i++)cout<<p[i].name<<":"<<p[i].id<<endl;return 0;
}bool find(int x)
{for(int i=1;i<=n;i++){if(line[x][i]==1&&used[i]==0){used[i]=1;if(g[i]==0||find(g[i])){b[x]=i;g[i]=x;return true;}}}return false;
}
//判断x能不能有别的匹配
bool check(int x)
{if(vis[x]==1)//走出回路return true;vis[x]=1;for(int i=1;i<=n;i++){if(used[i]==0&&line[x][i]&&g[i]!=x){//不是原匹配used[i]=1;if(g[i]==0||check(g[i]))return true;}}return false;
}这篇关于codevs1027 姓名与id的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
