自动搬运

查看原文

来自洛谷，原作者为

	未见堇开 是环境在影响着我。

搬运于2025-08-24 22:16:58，当前版本为作者最后更新于2020-02-10 07:48:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$2020-2-10\; \mathrm {Ver.}$

补集转化思想经典题目，值得一做。

也正是因此，我一直以为洛谷早就有这道题了。

暴力枚举求同色三角形的算法时间复杂度为$O(n^{3})$，看上去已经无法再优化。那么，我们能否将同色三角形的数目换成一个可以更快求得的量呢？

可以看出，同色三角形数目$=$三角形数目-异色三角形数目，而三角形数目为$\binom {n} {3}$，可以$\mathrm {O}(1)$求出。

考虑如何求异色三角形数目。

定义两边颜色不同的角为异色角。显然每个异色三角形中有两个异色角，且所有异色三角形的异色角都不属于其他异色三角形。

对每个点统计异色角的数目，再除以$2$即为异色三角形的数目。

时间复杂度$\Theta (n)$，可以通过此题。

答案是$O(n^{3})$级别的，别忘了开long long！

代码：

#include<cstdio>
#define reg register
#define MAXN 100001
using namespace std;

typedef long long ll;

int deg[MAXN];
ll ans=0;
int n,m;

int main()
{
    scanf("%d %d",&n,&m);
    for(reg int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        ++deg[u],++deg[v];
    }
    for(reg int i=1;i<=n;i++)
        ans+=(1ll*deg[i]*(n-1-deg[i]));
    printf("%lld",1ll*n*(n-1)*(n-2)/6-(ans>>1));
    return(0);
}