贝壳找房魔法师顾问

题意

来源:计算之道2018复赛d

贝壳找房在遥远的传奇境外,找到了一个强大的魔法师顾问。他有 22 串数量相同的法力水晶,每个法力水晶可能有不同的颜色。为了方便起见,可以将每串法力水晶视为一个长度不大于
$10^5$ ,字符集不大于 $10^5$ 的字符串。现在魔法师想要通过一系列魔法使得这两个字符串相同。每种魔法形如 $(u,\ v),\ u,\ v \le 10^5$ ,可以将一个字符$u$改成一个字符 $v$,并且可以使用无限次。出于种种原因,魔法师会强行指定这两个串能否进行修改。

若失败输出 -1,否则输出最少使用的魔法的种类数。

输入格式
一个正整数$n(n \le 10^5)$ 表示每个字符串的长度。

接下来两行每行首先输入一个单词(”Variable”或”Constant”),”Variable”表示这个字符串能进行修改,”Constant”表示这个字符串不能进行修改,然后n个正整数表示一个字符集不大于$10^5$ 的字符串。

分析

对于CC:直接比较即可。

对于VV:问题可以转化为给一张无向图,最少用几条边可以保持原图的联通性(可以新建)

每一个连通分量里面选n-1条边即可。

对于CV(VC):问题转化为给一张有向图,最少用几条边可以保持原图的连通性(可以新建)

对于每一个联通分量,如果里面不含强连通分量,则选n-1条边即可

如果里面含有强连通分量,则最少需要n条边 可以使这张图变为强连通。

对每个联通分量用拓扑排序判环。

代码

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e6 + 5;
string a[2][maxn];
string b[2] = {"Constant", "Variable"};
map<string, int> maps;
int par[maxn];
vector<int> G[maxn], GG[maxn];
bool vis[maxn];
int in[maxn];

inline int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }

void dfs(int id, int u) {
GG[id].pb(u);
vis[u] = true;
for (auto &v : G[u]) {
if (!vis[v]) {
dfs(id, v);
}
}
}
int topo(int id) {
queue<int> q;
int cnt = 0;
for (auto &v : GG[id]) {
if (!in[v]) {
q.push(v);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
cnt++;
for (auto &v : G[u]) {
if (in[v] > 0) {
in[v]--;
if (!in[v]) q.push(v);
}
}
}
if (cnt == GG[id].size())
return GG[id].size() - 1;
else
return GG[id].size();
}

int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
std::ios::sync_with_stdio(false);

int n;
while (cin >> n) {
string s[2];
for (int i = 0; i < 2; i++) {
cin >> s[i];
for (int k = 0; k < n; k++) cin >> a[i][k];
}
bool flag = true;
if (s[0] == b[0] && s[1] == b[0]) {
for (int i = 0; i < n; i++) {
if (a[0][i] != a[1][i]) {
flag = false;
break;
}
}
if (flag)
cout << 0 << endl;
else
cout << -1 << endl;
} else if (s[0] == b[1] && s[1] == b[1]) {
for (int i = 0; i < maxn; i++) par[i] = -1;
maps.clear();
int idx = 1;
for (int i = 0; i < n; i++) {
if (a[0][i] == a[1][i]) continue;
int u =
maps[a[0][i]] == 0 ? maps[a[0][i]] = idx++ : maps[a[0][i]];
int v =
maps[a[1][i]] == 0 ? maps[a[1][i]] = idx++ : maps[a[1][i]];
u = find(u);
v = find(v);
if (u != v) {
par[v] += par[u];
par[u] = v;
}
}
ll ans = 0;
for (int i = 1; i < idx; i++) {
if (par[i] < -1) {
ans += -par[i] - 1;
}
}
cout << ans << endl;
} else {
for (int i = 0; i < maxn; i++) par[i] = -1;
for (int i = 0; i < maxn; i++) G[i].clear(), GG[i].clear();
clr(in, 0);
clr(vis, 0);
maps.clear();
int idx = 1;
for (int i = 0; i < n; i++) {
if (a[0][i] == a[1][i]) continue;
int u =
maps[a[0][i]] == 0 ? maps[a[0][i]] = idx++ : maps[a[0][i]];
int v =
maps[a[1][i]] == 0 ? maps[a[1][i]] = idx++ : maps[a[1][i]];
G[u].pb(v);
in[v]++;
u = find(u);
v = find(v);
if(u != v)
par[v] = u;
}
int id = 0;
map<int,int> rt;
for(int i=1;i<idx;i++){
if(par[i] < 0){
rt[i] = id++;
}
}
ll ans = 0;
for (int i = 1; i < idx; i++) {
int u = find(i);
GG[rt[u]].pb(i);
}
for (int i = 0; i < id; i++) {
ans += topo(i);
}
cout << ans << endl;
}
}
}
Thank you for your support!