题意:找具有三条边颜色相同的三角形数

这个题数据比较水,直接暴力也能过,不过@freeloop建议我们用单色三角形理论去计算,于是看了别人的题解。大致就是先求出非单色三角形数目,然后用总的减去非单色三角形。总的数目是C(n,3),非单色三角形我们只需要遍历每个点,看看他的边是否具有同样颜色(这里要注意除以2,因为遍历三角形另外点的时候具有重复计算)就可以了。


题目地址:http://acm.scu.edu.cn/soj/problem/2090/


代码:

Memory: 1392 KB
Time: 36 MS
Language: C++ (G++-3)
Result: Accepted
#include <iostream>
#include <memory.h>
#include <cstdio>
using namespace std;
#define MAX 1010
int red[MAX];
int t, k, m, n, u, v, ans;
int main()
{
    scanf("%d", &k);
    while(k--){     
        memset(red, 0, sizeof(red));
        scanf("%d%d", &n, &m);
        while(m--){
            scanf("%d%d", &u, &v);
            red[u]++;
            red[v]++;
        }
        t = 0;
        for(int i=1;i<=n;i++)t+=red[i]*(n-red[i]-1);
        ans = n*(n-1)*(n-2)/6-t/2;
        printf("%d\n", ans);
    }
    return 0;
}