TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4252
  • 题目
  • P4252数三角形
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

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

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

    输入格式

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

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

    输出格式

    一行G的多样性得分。

    样例输入 1

    4 3
    1 2 1
    1 3 1
    2 3 1

    样例输出 1

    -6

    样例输入 2

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

    样例输出 2

    0

    提示


    对于 20%20\%20% 的数据,n≤500,m≤n(n−1)/2。

    对于 40%40\%40% 的数据,n≤2000,m≤n(n−1)/2。

    对于 100%100\%100% 的数据,n≤100000,m≤min(n(n−1)/2,200000)。
    样例解释 1

    (1,2,3)能组成一个同色三角形,找不到异色三角形,得分为 −6。
    样例解释 2

    (1,2,3) 能组成一个同色三角形,(1,2,4),(1,3,4) 能组成两个异色三角形,得分为 2∗3−6=0
    样例输入1

    4 3
    1 2 1
    1 3 1
    2 3 1