题解 CF229C Triangles

· · 题解

对于一个完全图，三角形的个数显然是 C(n,3)

现在把一些边挪到了另一个平面，那么就会有一些原本存在的三角形被拆掉了

我们选择把在原平面上的边染成红色，另一个平面上的边染成蓝色

这样就可以把两个平面变成一个了

样例大概长这样

那么我们要求的就是 三边全红 或者 三边全蓝 的三角形

直接数不好数，选择用 所有三角形的数量 - 不合法的三角形数量

那么问题就变成了求 不合法的三角形数量

显然不合法的三角形满足 两红一蓝 或者 一红两蓝

上面两个条件等价于 三条边中至少有一条红边和一条蓝边

考虑一个点 i ，假设它会往外面连 a_i 条红色边和 b_i 条蓝色边

由于每一条从 i 出发的红色边都可以和每一条从 i 出发的蓝色边构成一个不合法三角形

（由于一红一蓝已经满足了条件，我们并不需要去考虑第三条边的颜色）

所以这个点贡献的不合法三角形个数为 a_i \times b_i

但是这么算会有重复

拿样例来说，对于三角形 (2,3,5) ，点 2 做了一次贡献，点 3 做了一次贡献

点 5 由于两边都是蓝色所以没有贡献

因为 两红一蓝 或者 一红两蓝 的三角形中有且只有一个点的两条边都是同色的

所以只有两个点有贡献，一个三角形会被重复算两次

所以 ans=C(n,3)- \dfrac{\sum \limits_{i=1}^n a_i \times b_i}{2}

然后你就会发现 n^2 的边数直接统计 a_i 肯定就炸了

但因为是完全图，所以 a_i+b_i= n-1

所以 ans=C(n,3)- \dfrac{\sum \limits_{i=1}^n b_i \times (n-1-b_i)}{2}

只需要统计 b_i 即可

复杂度 \mathcal O(n+m)

#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;

const int N=1005000;

int n,m;
int b[N];
long long ans;

inline long long read(){
    long long re=0,k=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') k=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        re=re*10+ch-'0';
        ch=getchar();
    }
    return re*k;
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        b[x]++,b[y]++;
    }
    for(int i=1;i<=n;i++)   ans-=(long long)b[i]*(n-1-b[i]);
    ans=ans/2+(long long)(n-2)*(n-1)*n/6;
    printf("%lld\n",ans);
    return 0;
}