【枚举】【P9008】大碗宽面
一扶苏一
·
·
题解
【枚举】【P9008】大碗宽面
Description
给定一张 n 个点的图，两点之间要么有一条灰边（陌生人），要么连一条黑边（敌人），要么连一条白边（朋友）。黑边和白边共 m 条。
如果一个点对：
- 被一条白边连接
- 被一条灰边连接，且这个点对不属于任何三条边颜色均不同的三元环
则对答案造成 1 的贡献。求答案。
## Analysis
题目名不是我起的，但是题面是我写的。比赛时感觉创飞了不少人，倒开的选手也直接把这个题跳了。难道大家不喜欢 impart？
因为 $n$ 很大，直接枚举所有点对的梦想破灭了。考虑正难则反，尝试把没有贡献的点对数算出来，拿总的点对数 $n(n-1)/2$ 减一下即可。
首先黑边连接的点对没有贡献，然后被灰边连接的点对如果属于一个三色三元环也没有贡献。前者可以直接算，考虑后者怎么算。
灰边有 $O(n^2)$ 条，直接枚举是不行的，但是考虑黑边和白边数量很少。可以枚举每一条黑边 $(u,v)$，然后分别枚举连接 $v$ 和 $u$ 的白边。以枚举连接 $v$ 的白边 $(v,w)$ 为例，如果 $u$ 和 $w$ 之间是灰边，那么就可以把边 $(u,w)$ 的贡献减掉。因为一条边可能被算多次，所以减掉贡献一共要用一个 map 之类的容器随便记一下以后不要再扣这条边的贡献了。
考虑复杂度：枚举了 $O(m)$ 条黑边，对每条黑边枚举它两个端点连接的白边，至多 $O(m)$ 条，所以枚举量最坏 $O(m^2)$。每次需要去 map 里查一下，所以总复杂度是 $O(m^2 \log n)$。
## Code
```cpp
#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
const int maxn = 1000005;
int n, p, q;
std::map<std::pair<int, int>, bool> calced;
std::vector<int> enemy[maxn], frnds[maxn];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> p >> q;
long long ans = 1ll * n * (n - 1) / 2;
for (int i = 1, u, v; i <= p; ++i) {
std::cin >> u >> v;
frnds[u].push_back(v);
frnds[v].push_back(u);
calced[{u,v}] = calced[{v,u}] = true;
}
for (int i = 1, u, v; i <= q; ++i) {
std::cin >> u >> v;
enemy[u].push_back(v);
enemy[v].push_back(u);
--ans;
calced[{u,v}] = calced[{v,u}] = true;
}
for (int u = 1; u <= n; ++u) {
for (auto v : enemy[u]) {
for (auto w : frnds[u]) if (!calced[{w, v}]) {
calced[{w,v}] = calced[{v,w}] = true;
--ans;
}
for (auto w : frnds[v]) if (!calced[{w, u}]) {
calced[{w,u}] = calced[{u,w}] = true;
--ans;
}
}
}
std::cout << ans << std::endl;
}
```