NKOJ 4252 数三角形（乱搞）

发表于 |
字数统计: 583字 | 阅读时长 ≈ 3min

P4252数三角形

问题描述

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

现在，请你写一个程序来计算 G 的多样性分数。

输入格式

第一行两个正整数 n 和 m，其中 n 表示 G 中顶点的个数，m表示 G 中红色或者绿色的边的条数。

接下来 m行每行包括三个整数 a,b,c代表连接顶点 a和顶点 b的边颜色为红色 (c=1)或者绿色 (c=2)。

输出格式

一行G的多样性得分。

样例输入

4 3
1 2 1
1 3 1
2 3 1

样例输出

-6

此题纯属巧合。
令$Same$表示同色角的个数，$Dif$表示异色角的个数，同时令

$A=同色三角形的个数$
$B=有两边同色的三角形的个数$
$C=三边都异色的三角形的个数$

那么有
$Same=3\times A+B$
$Dif=2\times B+3\times C$
注意到我们要求的是$3\times C-6\times A$，那么就等于$Dif-2\times Same$

那么此题得解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define N 100005
#define ll long long
using namespace std;
ll n,m,cnt1,cnt2,cnt[N][3];
int main()
{
	ll i,j,x,y,z;
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		cnt[x][z]++;cnt[y][z]++;
	}
	for(i=1;i<=n;i++)
	{
		cnt[i][0]=n-1-cnt[i][1]-cnt[i][2];
		for(j=0;j<=2;j++)cnt1+=cnt[i][j]*(cnt[i][j]-1)/2;
		cnt2+=cnt[i][0]*cnt[i][1];
		cnt2+=cnt[i][0]*cnt[i][2];
		cnt2+=cnt[i][1]*cnt[i][2];
	}
	printf("%lld",cnt2-cnt1*2);
}