题解 P6057 【[加油武汉]七步洗手法】

· · 题解

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