UVALive5846

题目大意：见刘汝佳《算法竞赛入门经典——训练指南》P173。

解题思路：

　　如果要直接求所有单色三角形的个数似乎不简单，正难则反，先求出所有非单色三角形 cnt，answer = C（n,3）- cnt。

　　首先，对于每一个非单色三角形，一定有2个点对应一对异色边，那么我们只需要统计每一个点连接的红边或者蓝边数 t，则这个点连接的异色三角形个数为：t*（n - 1 - t），把各边的异色三角形个数加起来。按照这种方式，对于每一个非单色三角形我们都会从它的2个连接着一对异色边的点计算各一次，所以我们要将得到的异色三角形总数除以二就可以得到正确的 cnt。

AC代码：

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
typedef long long ll;
const int maxn=1003;
bool color[maxn][maxn];
int main()
{
    int T,tmp;
    int N;
    scanf("%d",&T);
    while(T--){
        ll t1=0;
        scanf("%d",&N);
        for(int i=1;i<N;i+=1){
            for(int j=i+1;j<=N;j+=1){
                scanf("%d",&tmp);
                if(tmp) color[i][j]=color[j][i]=true;
                else    color[i][j]=color[j][i]=false;
            }
        }
        for(int i=1;i<=N;i++){
            ll on=0;
            for(int j=1;j<=N;j++){
                if(i==j)    continue;
                if(color[i][j]) on++;
            }
            t1+=(on*(N-1-on));
        }
        ll ans=(ll)N*(N-2)*(N-1)/6-t1/2;
        printf("%lld
",ans);
    }
    return 0;
}