题意:有n(1<=n<=20)个人,每一个人在发电报的时候是以固定的绰号发送的,现在给定一串序列表示某个人进入房间,某个人从房间出去,或者截获了以
什么绰号发送的电报,问能否推出每个人对应的绰号是什么,如果推理不出来输出"???"。
题解:很容易想到二分匹配,但是正常思维构图之后会发现很难搞,因为一些明明矛盾的边的关系也搞进去了,类似于建反图的方法,每次把一定不会满足条件
的边去掉,最后剩下的边是可能满足的关系对,之后枚举每一个二分图中的必须边,如果删除后匹配数减少那么当前的匹配是正确的否则是不确定的。
Sure原创,转载请注明出处。
#include <iostream> #include <cstdio> #include <string> #include <memory.h> #include <map> #include <utility> #include <algorithm> using namespace std; const int maxn = 22; struct ANS { string sp,real; bool operator < (const ANS &other) const { return sp < other.sp; } }res[maxn]; string name[maxn]; int match[maxn],who[maxn],save[maxn]; bool vis[maxn],relation[maxn][maxn],in[maxn]; map <string , int> hash , room , spy; int m,n,top; void init() { hash.clear(); room.clear(); spy.clear(); top = m = 0; memset(who,-1,sizeof(who)); memset(relation,true,sizeof(relation)); return; } void read() { for(int i=1;i<=n;i++) { cin >> name[i]; hash[name[i]] = i; } return; } void make() { char str[3]; string ss; while(scanf("%s",str) && str[0] != 'Q') { cin >> ss; if(str[0] == 'E') { int tmp = spy[ss]; if(tmp == 0) { spy[ss] = ++m; tmp = m; } room[ss] = tmp; } else if(str[0] == 'L') room.erase(ss); else { memset(in,false,sizeof(in)); int v = hash[ss]; map <string , int>::iterator it; for(it = room.begin();it != room.end();it++) { in[(*it).second] = true; } for(int i=1;i<=n;i++) { if(in[i] == false) relation[i][v] = false; } } } return; } bool find(int u) { for(int i=1;i<=n;i++) { if(relation[u][i] && vis[i] == false) { vis[i] = true; if(match[i] == -1 || find(match[i])) { who[u] = i; match[i] = u; return true; } } } return false; } int hungary() { int cnt = 0; memset(match,-1,sizeof(match)); for(int i=1;i<=m;i++) { memset(vis,false,sizeof(vis)); if(find(i)) cnt++; } return cnt; } void solve() { int tot = hungary(); for(int i=1;i<=m;i++) { save[i] = who[i]; } map <string , int>::iterator it; for(it = spy.begin();it != spy.end();it++) { int u = (*it).second; res[top].sp = (*it).first; if(save[u] == -1) { res[top++].real = "???"; continue; } relation[u][save[u]] = false; if(hungary() < tot) res[top++].real = name[save[u]]; else res[top++].real = "???"; relation[u][save[u]] = true; } sort(res , res + top); for(int i=0;i<top;i++) { cout<<res[i].sp<<":"<<res[i].real<<endl; } return; } int main() { while(~scanf("%d",&n)) { init(); read(); make(); solve(); } return 0; }