Fifnmar edited 4 年前
要好好理解「敌人的敌人是朋友」这句话。重点分析一下把 add_rival(a, b) 的正确性。其实应该分四种情况讨论，但像我这么写的话就避免了显式的 if 判断（虽然有一定性能损失）。
void add_rival(u64 const a, u64 const b) {
connect(a, real_rival_of(b).value_or(a)); // real_rival_of returns an optional rival, if a is in no gang
connect(b, real_rival_of(a).value_or(b)); // returns nothing, in which case 2nd param. would be what's in value_or().
direct_rivals_[a] = real_boss_of(b);
direct_rivals_[b] = real_boss_of(a);
}
如果 a 和 b 都没有帮派：
前两行会把 a 和 a 自己连接起来，约等于无效。后两行设置好 rival 关系。
如果其中一个有帮派：
前两行会把不在帮派里的连接到相应帮派中去。后两行设置好 a 和 b 的 rival 关系（主要是那个新加入帮派的）。
如果两个都有帮派：
这种情况下最多可能涉及到四个帮派的关系。前两行把有共同敌人的帮派合并，后两行其实可有可无，是一个性能的 overhead。
上面这样的写法比较简洁所以我这么写了。两个赋值带来的 overhead 不一定就比 if 跳转和增大的代码长度的影响大哦（boki⭐）。
完整代码：
#include <iostream>
#include <vector>
#include <optional>
using namespace std;
using u64 = uint64_t;
class ConnectivitySet {
public:
ConnectivitySet(u64 const size) : direct_bosses_(size) {
for (u64 i = 0; i < size; ++i) {
direct_bosses_[i] = i;
}
}
void connect(u64 const a, u64 const b) {
auto const kRealBossA = real_boss_of(a);
auto const kRealBossB = real_boss_of(b);
direct_bosses_[kRealBossA] = kRealBossB;
}
bool is_connected(u64 const a, u64 const b) { return real_boss_of(a) == real_boss_of(b); }
private:
vector<u64> direct_bosses_;
protected:
u64 real_boss_of(u64 const a) {
if (direct_bosses_[a] == a) {
return a;
}
return direct_bosses_[a] = real_boss_of(direct_bosses_[a]);
}
};
class GangRival : protected ConnectivitySet {
public:
GangRival(u64 size) : ConnectivitySet(size), direct_rivals_(size) {}
void add_rival(u64 const a, u64 const b) {
connect(a, real_rival_of(b).value_or(a));
connect(b, real_rival_of(a).value_or(b)); // if no rival do not connect (connect with self)
direct_rivals_[a] = real_boss_of(b);
direct_rivals_[b] = real_boss_of(a);
}
enum class GangMemberRelation { kNull, kFriend, kRival };
GangMemberRelation query(u64 const a, u64 const b) {
auto const kRealBossOfA = real_boss_of(a);
auto const kRealBossOfB = real_boss_of(b);
if (kRealBossOfA == kRealBossOfB) {
return GangMemberRelation::kFriend;
}
if (real_rival_of(kRealBossOfA) == kRealBossOfB) {
return GangMemberRelation::kRival;
}
return GangMemberRelation::kNull;
}
private:
vector<optional<u64>> direct_rivals_;
bool not_in_gang(u64 const kMemberId) const { return direct_rivals_[kMemberId] == nullopt; }
optional<u64> real_rival_of(u64 const a) {
if (direct_rivals_[a] == nullopt) {
return nullopt;
}
return real_boss_of(direct_rivals_[a].value());
}
};
int main()
u64 t;
cin >> t;
for (u64 i = 0; i < t; ++i) {
u64 n, m;
cin >> n >> m;
GangRival gr_set(n);
for (u64 i = 0; i < m; ++i) {
char kOrder[2];
u64 a, b;
cin >> kOrder >> a >> b;
a -= 1, b -= 1;
switch (*kOrder) {
case 'A': {
gr_set.add_rival(a, b);
} break;
case 'Q': {
switch (gr_set.query(a, b)) {
case GangRival::GangMemberRelation::kFriend: {
cout << "In the same gang.\n";
} break;
case GangRival::GangMemberRelation::kNull: {
cout << "Not sure yet.\n";
} break;
case GangRival::GangMemberRelation::kRival: {
cout << "In different gangs.\n";
} break;
}
} break;
}
}
}
}
呃，发现代码里夹了一个
not_in_gang的legacy code……