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

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

【输出格式】
一行,$G$的多样性得分。

【数据范围】
$n \le 100000, m \le min(\frac{n(n-1)}{2},200000)$。

也就是说 请你$O(n)$解决此题

下面来看看正解的思路:

设$a$表示两条邻边颜色不相同的角的个数,$b$表示两条邻边颜色相同的角的个数。
三角形有三种,第一种是三边各不相同的,设数目为$x$,第二种是三边全部相同的,设它为$y$,剩下的都是两边相同,一边不同的,设它为$z$。
每个$x$型三角形有$3$个$a$型角,$0$个$b$型角; 每个$y$型三角形有$0$个$a$型角,$3$个$b$型角; 每个$z$型三角形有$2$个$a$型角,$1$个$b$型角。
所以$a=3x+2z, b=3y+z$
而我们要求的正好是$a-2b$,即$a-2b=3x+2z-2*(3y-z)=3x-6y$

$a, b$都是很好求的,组合数算一算
【代码实现】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

ll n, m, ans;
ll a, b;
ll num[100005][3];

int main() {
scanf("%lld %lld", &n, &m);
for (int i = 1; i <= m; i++) {
ll x, y, z;
scanf("%lld %lld %lld", &x, &y, &z);
num[x][z]++; num[y][z]++;
}
for (int i = 1; i <= n; i++) {
num[i][0] = n - 1 - num[i][1] - num[i][2];
a = a + num[i][0] * num[i][1] + num[i][1] * num[i][2] + num[i][2] * num[i][0];
b = b + (num[i][0] * (num[i][0] - 1) / 2) + (num[i][1] * (num[i][1] - 1) / 2) + (num[i][2] * (num[i][2] - 1) / 2);
}
printf("%lld\n", a - 2 * b);
return 0;
}

评论