题意:
http://codeforces.com/problemset/problem/229/C
给你一个全图,分成两部分,问你这两个途中一共有多少个三角形.
思路:
如果是一个完整的全图,那么三角形的个数就是 C(n中取3),那么答案就是C(n中取3)减去被破坏的三角形个数,这个题目关键的一点就是全图,全图中的每一个点的度数都是n-1,那么在其中的一个图中的度数是 a的话,另一个图中的度数就是 n - 1 - a,而每一个图中点的度数就是他的边数,想像一下吧两个图组合到一起的话就一定会另外形成 a * (n - 1 - a)个三角形,因为假如一个点连出去两条边(这两条边在两个图中),而那两条边又一定会被一条边相连接(因为是全图),就这样根据给的图就可以算出每一个点所在被破坏三角形的个数,需要注意一点的就是每一个破坏的三角形肯定是一条边在一个集合,而另两条边在另一个集合,那么这个破坏的三角形的三个点就一定是有两个点既在图1中有边,也在图二中有边,所以算了两次,所以要把所有被破坏的三角形个数除以二,在用总的个数减去破坏的个数就是答案..
#include<stdio.h>
#include<string.h>
#define N 1000000 + 1000
__int64 deg[N];
int main ()
{
int n ,m ,i ,a ,b;
__int64 sum ,s;
while(~scanf("%d %d" ,&n ,&m))
{
memset(deg ,0 ,sizeof(deg));
for(i = 1 ;i <= m ;i ++)
{
scanf("%d %d" ,&a ,&b);
deg[a] ++ ,deg[b] ++;
}
__int64 nn = n;
sum = 0;
for(i = 1 ;i <= n ;i ++)
{
sum += deg[i] * (nn - 1 - deg[i]);
}
printf("%I64d
" ,nn * (nn - 1) * (nn - 2) / 6 - sum / 2);
}
return 0;
}