计蒜客【NOIP2017模拟3】数三角形 <计数>

Problem

【NOIP2017模拟3】数三角形

Description

刚刚上高中的洁洁在学习组合数学的过程中遇到一道麻烦的题目，她希望你能帮助她解决。给定一张无向完全图，其中大部分边被染成蓝色，但也有一些边被染成红色或者绿色。现在，洁洁需要给这张图的多样性进行打分。一张图的多样性取决于它的同色和异色三角形的个数。具体来说，中每有一个三边颜色都互不同的三角形（异色三角形）可以得分，每有一个三边颜色都相同的三角形（同色三角形）则要被扣掉分，其它三角形不得分也不扣分。
现在，请你写一个程序来计算的多样性分数。

Input

第一行两个正整数和，其中表示中顶点的个数，表示中红色或者绿色的边的条数。
接下来行每行包括三个整数，代表连接顶点和顶点的边颜色为红色或者绿色。

Output

一行，的多样性得分。

Sample Input

Input #1

Input #2

Sample Output

Output #1

-6

Output #2

Hint

Explanation #1
能组成一个同色三角形，找不到异色三角形，得分为。
Explanation #2
能组成一个同色三角形，能组成两个异色三角形，得分为。

Constraint

对于的数据，。
对于的数据，。
对于的数据，。

Source

2017 NOIP 提高组模拟赛（三）Day2

标签：计数

Solution

整体代换，这类套路的标准做法。

定义同色角为无序三元组，其中为一个点，均连向这个点，且颜色相同。

定义异色角为无序三元组，其中为一个点，均连向这个点，且颜色不同。

显然同色角和异色角的个数是可以枚举计算的。对每个点记录其红色邻边的个数，蓝色邻边的个数，绿色邻边的个数，则同色角个数，异色角个数。

设有三种颜色的三角形有个，两种颜色的三角形有个，一种颜色的三角形有个。对于有三种颜色的三角形，其三个角均为异色角，对于有两种颜色的三角形，其有两个异色角和一个同色角，而对于只有一种颜色的三角形，其三个角均为同色角。因此，有

注意到所求值为，而用下式减去两倍上式正好得到。因此答案为。
对每个点统计其三种颜色的邻边个数即可。时间复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, s[MAX_N+5][3];
int main() {
    read(n), read(m); lnt A = 0, B = 0;
    for (int i = 1, u, v, c; i <= m; i++)
        read(u), read(v), read(c), s[u][c]++, s[v][c]++;
    for (int i = 1; i <= n; i++)
        s[i][0] = n-1-s[i][1]-s[i][2];
    for (int i = 1; i <= n; i++)
        A += 1LL*s[i][0]*s[i][1], 
        A += 1LL*s[i][0]*s[i][2], 
        A += 1LL*s[i][1]*s[i][2], 
        B += 1LL*s[i][0]*(s[i][0]-1)/2, 
        B += 1LL*s[i][1]*(s[i][1]-1)/2, 
        B += 1LL*s[i][2]*(s[i][2]-1)/2;
    return printf("%lld\n", A-2*B), 0;
}