Shen Huang's Blog
0%

POJ 1043 What's In A Name? (判断二分图最大匹配的必须边)

Posted on Edited on 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
using namespace std;

const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
#define maxn 110

int x[maxn],y[maxn];
int g[maxn][maxn];
bool vis[maxn];
int zero,n,m,k,nx,ny;
 map <string, int> mp1;            // 用来保存用户名 
 map <string, int> mp2;            // 用来记录代号 
char str[100][100];
string str2[100];
set< int >cur;                    // set 的插入与消去，好好用，第一次实用 
pair< string, int >pair1[100];    // 20-21 解的保存，pair的第一次实用 
int os[100];
bool path(int u){
	for (int v = 1; v <= ny; v ++){
		if (g[u][v] && !vis[v]){
			vis[v] = 1;
			if (y[v] == -1 || path(y[v])){
				x[u] = v;
				y[v] = u;
				return true;
			}
		}
	}
	return false;
}

int MaxMatch(){
	int ans = 0;
	//if (zero == k) {puts("0");return;} 
	memset(x, -1, sizeof(x));
	memset(y, -1, sizeof(y));
	for (int i = 1; i <= nx; i ++){
		if (x[i] == -1){
			memset(vis, 0, sizeof(vis));
			if (path(i)){
				ans ++;
			}
		}
	}
	return ans;
}

int main(){
	int n;

	cin >> n;
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= n; j ++) g[i][j] = 1;
	for (int i = 1; i <= n; i ++){
		scanf("%s",str[i]);
		mp1[str[i]] = i;
	}

	int cnt = 0;
	char sign[10],name[100];
	while (scanf("%s",sign) && sign[0] != &#39;Q&#39;){
		scanf("%s", name);
		if (sign[0] == &#39;E&#39;){

			if (mp2[name] == 0){
				mp2[name] = ++cnt;
				str2[cnt] = name;
			}
			int y = mp2[name];
			cur.insert(y);
		}else if (sign[0] == &#39;L&#39;){
			int y = mp2[name];
			cur.erase(y);
		}else {
			int x = mp1[name];

			for (int i = 1; i <= n; i ++){
				if (cur.find(i) == cur.end()){
					g[x][i] = 0;
				}
			}

		}
	}
	nx = ny = n;

	int mat = MaxMatch();
	//cout << mat << endl;
	for (int i = 1; i <= n; i ++){
		pair1[i] = mp(str2[i],i);
		os[i] = 0;
		for (int j = 1; j <= n; j ++){
			if (g[j][i]){
				g[j][i] = 0;
				int tmp = MaxMatch();
				//cout << tmp << endl;
				if (tmp != mat){
					os[i] = j;
				}
				g[j][i] = 1;
			}
		}
	}
	sort( pair1 + 1, pair1 + n +1 );    // 对解的排序 
	int i, j;
    for( i = 1; i <= n; i++ )
    {
		cout<< pair1[i].first << ":"; 
    	if( os[pair1[i].second] == 0 )
            cout<< "???" << endl; 
    	else 
            cout<< str[os[pair1[i].second]] << endl; 
     }
	return 0;
}