【容斥补集转化】单色三角形问题

【描述】 有n个顶点的凸多边形，每个顶点两两之间有一条边，有m条红色的边，以及给出红色边的两边顶点编号，输出其中边颜色都相同的三角形的个数。 ($n<=1000$)

【思路】

这道题思路很是清奇。考虑暴力，自然是$O(n^3)$暴力枚举，如果你有梦想，由于判断的常数极小，所以是有可能过的。 考虑优化，我们考虑计算枚举每个顶点，计算单色三角形数目。但是问题就来了。我们的确可以枚举边，我们可以知道这夹这个顶点的两条边的颜色，但是这个顶点的对边呢？我们不可能知道对边的颜色，否则就变回$O(n^3)$暴力了。所以直接计算单色三角形是不方便的。考虑计算补集，我们计算不是单色三角形的三角形个数，再用全集减去之。这时我们再枚举每个顶点，我们发现，我们只要保证夹边颜色不同即可，对于对边，我们不关心它的颜色。所以我们用黑边数量乘红边数量就是这个顶点的答案。我们再来考虑一下，对于一个多色三角形，我们将会在两个顶点考虑它，所以我们需要把补集的答案除以2。时间复杂度$O(n)$。 代码：

#include<bits/stdc++.h> #define re register using namespace std; const int N=2e3+5; int n,m,a,b,c; inline int red(){ int data=0;int w=1; char ch=0; ch=getchar(); while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); if(ch=='-') w=-1,ch=getchar(); while(ch>='0' && ch<='9') data=(data<<3)+(data<<1)+ch-'0',ch=getchar(); return data*w; } int w[N],ans=0,ret=0; int main(){ n=red();m=red();ans=n*(n-1)*(n-2)/6; for(int re i=1;i<=m;i++)w[red()]++,w[red()]++; for(int re i=1;i<=n;i++)ret+=(n-1-w[i])*w[i]; cout<<ans-(ret>>1); }