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

Problem

【NOIP2017模拟3】数三角形

$\mathrm{Time\;Limit:\;3000\;ms}$
$\mathrm{Memory\;Limit:\;262144\;K}$

Description

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

Input

第一行两个正整数 $n$ 和 $m$，其中 $n$ 表示 $G$ 中顶点的个数，$m$ 表示 $G$ 中红色或者绿色的边的条数。
接下来 $m$ 行每行包括三个整数 $a,b,c$，代表连接顶点 $a$ 和顶点 $b$ 的边颜色为红色 $(c=1)$ 或者绿色 $(c=2)$。

Output

一行，$G$ 的多样性得分。

Sample Input

Input #1

4 3
1 2 1
1 3 1
2 3 1

Input #2

4 4
1 2 1
1 3 1
2 3 1
1 4 2

Sample Output

Output #1

-6

Output #2

0

Hint

Explanation #1
$(1,2,3)$ 能组成一个同色三角形，找不到异色三角形，得分为 $-6$。
Explanation #2
$(1,2,3)$ 能组成一个同色三角形，$(1,2,4),(1,3,4)(1,2,4),(1,3,4)$ 能组成两个异色三角形，得分为 $2*3-6=0$。

Constraint

对于 $20\%$ 的数据，$n \le 500,m \le \frac{n(n-1)}{2}$。
对于 $40\%$ 的数据，$n \le 2000,m \le \frac{n(n-1)}{2}$。
对于 $100\%$ 的数据，$n \le 100000, m \le \min(\frac{n(n-1)}{2},200000)$。

Source

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

标签：计数

Solution

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

定义同色角为无序三元组$(v,e_1,e_2)$，其中$v$为一个点，$e_1,e_2$均连向这个点，且$e_1,e_2$颜色相同。

定义异色角为无序三元组$(v,e_1,e_2)$，其中$v$为一个点，$e_1,e_2$均连向这个点，且$e_1,e_2$颜色不同。

显然同色角和异色角的个数是可以枚举$v$计算的。对每个点记录其红色邻边的个数$R_i$，蓝色邻边的个数$B_i$，绿色邻边的个数$G_i$，则同色角个数$X=\sum_{i=1}^{n}(\frac{R_i(R_i-1)}{2}+\frac{B_i(B_i-1)}{2}+\frac{G_i(G_i-1)}{2})$，异色角个数$Y=\sum_{i=1}^{n}(R_iG_i+R_iB_i+G_iB_i)$。

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

$$\begin{cases} Q+3R=X\\ 3P+2Q=Y\\ \end{cases}$$

注意到所求值为$3P-6R$，而用下式减去两倍上式正好得到$3P-6R=Y-2X$。因此答案为$异色角个数-2\times 同色角个数$。
对每个点统计其三种颜色的邻边个数即可。时间复杂度$\mathcal{O}(n)$。

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;
}