BZOJ 2916([Poi1997]Monochromatic Triangles-容斥+组合数学)

2916: [Poi1997]Monochromatic Triangles
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 13 Solved: 8
[Submit][Status]
Description
空间中有n个点，任意3个点不共线。每两个点用红线或者蓝线连接，如果一个三角形的三边颜色相同，那么称为同色三角形。给你一组数据，计算同色三角形的总数。


Input

第一行是整数n, 3 <= n <= 1000,点的个数。

第二行是整数m, 0 <= m <= 250000,红线数目。

接下来的m行，每行两个数p和k，1 <= p < k <= n。表示一条红线的两个端点。

Output

一个整数，单色三角形的数目。

Sample Input
6

9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6

Sample Output
2
HINT

Source

[Submit][Status]

转化为求不同色三角形数=总三角形-同色三角形

一个不同色三角形：1红2蓝，1蓝2红 推论：一定有且只有2个点的邻边颜色不同

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i #define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (1000+10)
#define MAXM (250000+10)
int n,m,a[MAXN];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>m;
For(i,m)
{
int u,v;
scanf("%d%d",&u,&v);
a[u]++,a[v]++;
}
long long ans=(long long)n*(n-1)*(n-2)/6;
For(i,n) ans-=a[i]*(n-a[i]-1)/2;
cout< return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i #define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MEM(a) memset(a,0,sizeof(a))
#define MEMI(a) memset(a,127,sizeof(a))
#define MEMi(a) memset(a,128,sizeof(a))
#define INF (2139062143)
#define F (1000000009)
#define MAXN (1000+10)
#define MAXM (250000+10)
int n,m,a[MAXN];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>m;
For(i,m)
{
int u,v;
scanf("%d%d",&u,&v);
a[u]++,a[v]++;
}
long long ans=(long long)n*(n-1)*(n-2)/6;
For(i,n) ans-=a[i]*(n-a[i]-1)/2;
cout< return 0;
}