[codevs1027]姓名与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不能确定，输出???。
按照姓名的字典顺序输出。
输入示例
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
数据规模及约定
见“输入”，还有操作数可以达到 10^5 左右。
题解
首先可以想到姓名和 ID 进行二分图匹配，现在难点在于判断唯一性。
跑完二分图匹配后，我们逐个判断，对于一个姓名 i，我们强制不让它匹配它当前的匹配对象，在此基础上再跑一遍二分图，若还是完全匹配，则说明姓名 i 不能被唯一确定，标记成“???”。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <map>
using namespace std;int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}#define maxn 45
#define maxm 3210
#define oo 2147483647
struct Edge {
int from, to, flow;
Edge() {}
Edge(int _1, int _2, int _3): from(_1), to(_2), flow(_3) {}
} ;
struct Dinic {
int n, m, s, t, head[maxn], next[maxm];
Edge es[maxm];
int hd, tl, Q[maxn], vis[maxn];
int cur[maxn];
void cpy(Dinic& T) {
n = T.n; m = T.m; s = T.s; t = T.t;
memcpy(head, T.head, sizeof(head));
memcpy(next, T.next, sizeof(next));
for(int i = 0; i < m; i++) es[i] = T.es[i];
return ;
}
void init(int nn) {
n = nn; m = 0;
memset(head, -1, sizeof(head));
return ;
}
void AddEdge(int a, int b, int c) {
es[m] = Edge(a, b, c); next[m] = head[a]; head[a] = m++;
es[m] = Edge(b, a, 0); next[m] = head[b]; head[b] = m++;
return ;
}
bool BFS() {
memset(vis, 0, sizeof(vis)); vis[s] = 1;
hd = tl = 0; Q[++tl] = s;
while(hd < tl) {
int u = Q[++hd];
for(int i = head[u]; i != -1; i = next[i]) {
Edge& e = es[i];
if(!vis[e.to] && e.flow) {
vis[e.to] = vis[u] + 1;
Q[++tl] = e.to;
}
}
}
return vis[t] > 1;
}
int DFS(int u, int a) {
if(u == t || !a) return a;
int flow = 0, f;
for(int& i = cur[u]; i != -1; i = next[i]) {
Edge& e = es[i];
if(vis[e.to] == vis[u] + 1 && (f = DFS(e.to, min(a, e.flow)))) {
flow += f; a -= f;
e.flow -= f; es[i^1].flow += f;
if(!a) return flow;
}
}
return flow;
}
int MaxFlow(int ss, int tt) {
s = ss; t = tt;
int flow = 0;
while(BFS()) {
for(int i = 1; i <= n; i++) cur[i] = head[i];
flow += DFS(s, oo);
}
return flow;
}
} sol, sol2, sol3;#define maxp 25
string ID[maxp], name[maxp];
map <string, int> M, M2;
bool S[maxp];
int en[maxn][maxn];
struct Info {
string name, ID;
Info() {}
Info(string _, string __): name(_), ID(__) {}
bool operator < (const Info& t) const { return name < t.name; }
} is[maxp];int main() {
int n = read();
sol.init((n << 1) + 2); int s = (n << 1) + 1, t = s + 1;
for(int i = 1; i <= n; i++) cin >> ID[i];
sort(ID + 1, ID + n + 1);
for(int i = 1; i <= n; i++) M[ID[i]] = i;
int cp = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) en[i][j+n] = en[j+n][i] = 1;
while(1) {
char tc[2]; scanf("%s", tc);
if(tc[0] == 'Q') break;
string t; cin >> t;
if(tc[0] == 'E') {
if(!M2.count(t)) M2[t] = ++cp, name[cp] = t;
S[M2[t]] = 1;
}
if(tc[0] == 'L') S[M2[t]] = 0;
if(tc[0] == 'M') {
int p = M[t];
for(int i = 1; i <= n; i++) if(!S[i]) en[i][p+n] = en[p+n][i] = -1;
}
}
int ce = 0;
for(int i = 1; i <= cp; i++)
for(int j = n + 1; j <= (n << 1); j++) if(en[i][j] > 0)
sol.AddEdge(i, j, 1), en[i][j] = ce, ce += 2;
for(int i = 1; i <= cp; i++) sol.AddEdge(s, i, 1);
for(int i = 1; i <= n; i++) sol.AddEdge(i + n, t, 1);
sol3.cpy(sol); sol2.cpy(sol);
int ans = sol.MaxFlow(s, t);
for(int i = 1; i <= cp; i++) {
for(int j = n + 1; j <= (n << 1); j++) if(en[i][j] >= 0 && !sol.es[en[i][j]].flow) {
sol2.cpy(sol3);
sol2.es[en[i][j]].flow = 0;
int tmp = sol2.MaxFlow(s, t);
//printf("tmp: %d\n", tmp);
if(tmp == ans) is[i] = Info(name[i], string("???"));
else is[i] = Info(name[i], ID[j-n]);
break;
}
}sort(is + 1, is + cp + 1);
for(int i = 1; i <= cp; i++) cout << is[i].name << ':' << is[i].ID << endl;return 0;
}
