Codes, Notes & Scribbles

There are n points given in a space. There are no three points, such that they lie on the same straight line. Each pair of points is connected by a segment coloured red or black. Each triangle, whose sides have the same colour is called a monochromatic triangle. We are given a list of all red segments and we want to find the number of all monochromatic triangles.

Task

• reads from the text file TRO.IN the following data: the number of points, the number of red segments and their list,
• finds the number of monochromatic triangles,
• writes the result to the text file TRO.OUT.

Input

In the second line of the same file there is one integer m, 0 <= m <= 250000, which equals the number of red segments.

In each of the following m lines there are two integers p and k separated by a single space, 1 <= p < k <= n. They are numbers of vertices which are ends of a red segment.

Output

Example

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

 2

Solution

按照ghost的建议开始看一些组合数学的东西了，挺难但是也很有趣啊~

这道经典题就作为我做这类题目的开始吧。

#include <cstdio>
using namespace std;
int main(){
	FILE *fin = fopen("TRO.IN","r"),*fout = fopen("TRO.OUT","w");
	long n,//the number of points
		m,//the number of red segments
		red[1001]={0},//the number of red segments connected to each point
		mono_sum=0;//the sum of monochromatic triangles
	fscanf(fin,"%ld%ld",&n,&m);
	mono_sum=(n-2)*(n-1)*n/6;
	for(long p,k;m>0;m--,red[p]++,red[k]++)	fscanf(fin,"%ld%ld",&p,&k);
	for(int i=1;i<=n;i++)	mono_sum-=(red[i]*(n-red[i]-1)/2);
	fprintf(fout,"%ld\n",mono_sum);
	fclose(fin);fclose(fout);
	return 0;
}

---

可能你对下面的文章也感兴趣：

• [ZOJ1610]Count the Colors
• [URAL1028]Stars (Using SBT, SBST, VBST)
• [POI VII] Promotion
• [POI VI Stage 1 Problem 1] Musketeers
• [POI IX] Railways