题目内容:
平面上有n个点(n≤8000),每两个点之间都有一条红色或者是黑色的线段,任意三点均不共线。 现在,已知哪些点之间连的线段是红色的,剩下的线段都是黑色的,要求计算这些点组成的三角 形中有多少是同色的(顶点编号从1到n)?
输入描述
第一行是n, m(3≤n≤8000),n表示点的个数,m表示红色线段的条数。下面m行,每 一行都是两个整数a和b,表示点a和点b之间的线段是红色的(a<b)。
输出描述
只有一行,表示同色三角形的个数。 提示:本题输出数据可能会超出长整数(long int)的范围。
输入样例
6 5 1 2 1 3 2 3 2 5 3 6
输出样例
7
思路:暴力枚举所有三角形来判断。
#include <iostream> using namespace std; int x[8005][8005]; //不为零为红线 int main(){ int n, m, a, b; cin >> n >> m; for(int i = 1; i <= m; i++){ cin >> a >> b; x[a][b] = 1; x[b][a] = 1; } int count = 0; for(int i = 1; i <= n - 2; i++){ for(int j = i + 1; j <= n - 1; j++){ for(int k = j + 1; k <= n; k++){ if(x[i][j] == x[j][k] && x[j][k] == x[i][k]) count++; } } } cout << count; return 0; }