【HDOJ】1914 The Stable Marriage Problem
10052 ワード
安定した結婚問題、Gale-Shapleyアルゴリズムは解くことができます.
1 /* 1914 */
2 #include <iostream>
3 #include <sstream>
4 #include <string>
5 #include <map>
6 #include <queue>
7 #include <set>
8 #include <stack>
9 #include <vector>
10 #include <deque>
11 #include <algorithm>
12 #include <cstdio>
13 #include <cmath>
14 #include <ctime>
15 #include <cstring>
16 #include <climits>
17 #include <cctype>
18 #include <cassert>
19 #include <functional>
20 #include <iterator>
21 #include <iomanip>
22 using namespace std;
23 //#pragma comment(linker,"/STACK:102400000,1024000")
24
25 #define sti set<int>
26 #define stpii set<pair<int, int> >
27 #define mpii map<int,int>
28 #define vi vector<int>
29 #define pii pair<int,int>
30 #define vpii vector<pair<int,int> >
31 #define rep(i, a, n) for (int i=a;i<n;++i)
32 #define per(i, a, n) for (int i=n-1;i>=a;--i)
33 #define clr clear
34 #define pb push_back
35 #define mp make_pair
36 #define fir first
37 #define sec second
38 #define all(x) (x).begin(),(x).end()
39 #define SZ(x) ((int)(x).size())
40 #define lson l, mid, rt<<1
41 #define rson mid+1, r, rt<<1|1
42
43 const int maxn = 30;
44 char s[40];
45 char wname[40];
46 int pref[maxn][maxn];
47 int order[maxn][maxn];
48 int nxt[maxn];
49 int future_husband[maxn];
50 int future_wife[maxn];
51 queue<int> Q;
52 int n;
53 int ID[128];
54
55 void engage(int man, int woman) {
56 int m = future_husband[woman];
57
58 if (m) {
59 future_wife[m] = 0;
60 Q.push(m);
61 }
62
63 future_husband[woman] = man;
64 future_wife[man] = woman;
65 }
66
67 void solve() {
68 while (!Q.empty()) {
69 int man = Q.front();
70 Q.pop();
71 int woman = pref[man][nxt[man]++];
72 if (!future_husband[woman]) {
73 engage(man, woman);
74 } else if (order[woman][man] < order[woman][future_husband[woman]]) {
75 engage(man, woman);
76 } else {
77 Q.push(man);
78 }
79 }
80
81 rep(i, 'a', 'z'+1) {
82 if (!ID[i])
83 continue;
84 printf("%c %c
", i, wname[future_wife[ID[i]]]);
85 }
86 }
87
88 int main() {
89 ios::sync_with_stdio(false);
90 #ifndef ONLINE_JUDGE
91 freopen("data.in", "r", stdin);
92 freopen("data.out", "w", stdout);
93 #endif
94
95 int t;
96 int nlc, nuc;
97
98 scanf("%d", &t);
99 while (t--) {
100 scanf("%d", &n);
101 memset(ID, 0, sizeof(ID));
102 nlc = nuc = 0;
103 rep(i, 0, n+n) {
104 scanf("%s", s);
105 if (islower(s[0])) {
106 ID[s[0]] = ++nlc;
107 } else {
108 ID[s[0]] = ++nuc;
109 wname[nuc] = s[0];
110 }
111 }
112
113 while (!Q.empty())
114 Q.pop();
115
116 int lid, uid;
117
118 rep(i, 0, n) {
119 scanf("%s", s);
120 lid = ID[s[0]];
121 rep(j, 1, n+1) {
122 uid = ID[s[1+j]];
123 pref[lid][j] = uid;
124 }
125 nxt[lid] = 1;
126 future_wife[lid] = 0;
127 Q.push(lid);
128 }
129
130 rep(i, 0, n) {
131 scanf("%s", s);
132 uid = ID[s[0]];
133 rep(j, 1, n+1) {
134 lid = ID[s[1+j]];
135 order[uid][lid] = j;
136 }
137 future_husband[uid] = 0;
138 }
139 solve();
140 if (t)
141 putchar('
');
142 }
143
144 #ifndef ONLINE_JUDGE
145 printf("time = %d.
", (int)clock());
146 #endif
147
148 return 0;
149 }