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<cstdio>  
#include<cstdlib>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<functional>  
#include<cmath>  
#include<cctype>  
using namespace std; 
#define For(i,n) for(int i=1;i<=n;i++)  
#define Rep(i,n) for(int i=0;i<n;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<<ans<<endl; 
    return 0; 
} 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<cctype>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;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<<ans<<endl;
 return 0;
}