POI 1997 单色三角形 Monochromatic triangles
O(N^3)的枚举是无法忍受的，这道题可以从反面考虑。单色三角形的个数就是全部的三角形的个数减去不同色三角形的个数。
在一个不同色的三角形中，显然有两个顶点，每个顶点连着这个三角形内的不同颜色的两条边。一个顶点出发有N-1条边，如果顶点i连接着D[i]条红边，那么它一定连接着(N-1-D[i])条黑边，这个顶点在D[i](N-1-D[i])个不同色三角形内。而一个顶点在一个三角形内被计算了两次，所以整个图中一共有 Sum{ D[i](N-1-D[i])/2 | i=1..N }个不同色三角形。
由于一共有C(N,3)个三角形，所以结果就是
C(N,3) - Sum{ D[i]*(N-1-D[i])/2 | i=1..N }
/*
* Problem: POI1997 tro
* Author: Guo Jiabao
* Time: 2008.11.28 19:45:22
* State: Solved
*/
#include <iostream>
#include <stdio.h>
using namespace std;
const int MAX=1001;
int D[MAX];
int N,M,Ans;
void init()
{
int i,a;
freopen("tro.in","r",stdin);
freopen("tro.out","w",stdout);
scanf("%d%d",&N,&M);
for (i=1;i<=M*2;i++)
{
scanf("%d",&a);
D[a]++;
}
}
void solve()
{
int i,T,S,A;
T=N*(N-1)*(N-2)/6;
S=0;
for (i=1;i<=N;i++)
{
A=D[i]*(N-1-D[i]);
S+=A/2;
}
Ans=T-S;
}
int main()
{
init();
solve();
cout << Ans;
return 0;
}
单色三角形
在空间中给出了n个点。这些点任三点不共线，并且每两个点之间都有一条线相连，每一条线不是红的就是黑的。在这些点和线组成的三角形中，如果一个三角形的三条边的颜色都相同，那么我们就称这个三角形为单色三角形。现给出所有涂红色的线，试求出单色三角形的数目。
任务：
请写一个程序：
从文本文件中读入点数和对红色连线的描述；
找出该图中红色三角形的数目；
把结果输出到文件TRO.OUT中。
输入格式：
在文本文件TRO.IN的第一行包括一个整数n，3 <= n <= 1000，为空间中的点数。
该文件的第二行为一个整数m，0 <= m <= 250000，为红色连线的数目。
以下的m行中每行为两个用空格分开的整数p和k，1 <= p < k <= n，表示第p点和第k号点之间的连线为红色。
输出格式：
你应该在文本文件TRO.OUT输出唯一的一个整数——同色三角形的数目。
样例：
输入
6
9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6
输出
2
上次修改时间 2017-02-03