自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 22:44:31，当前版本为作者最后更新于2023-02-05 21:41:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【枚举】【P9008】大碗宽面

Description

给定一张 $n$ 个点的图，两点之间要么有一条灰边（陌生人），要么连一条黑边（敌人），要么连一条白边（朋友）。黑边和白边共 $m$ 条。

如果一个点对：

1. 被一条白边连接
2. 被一条灰边连接，且这个点对不属于任何三条边颜色均不同的三元环

则对答案造成 $1$ 的贡献。求答案。

$1 \leq n \leq 10^6$，$1 \leq m \leq 10^3$。

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

#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;
}