编程介的小学生
2018-12-14 05:01
采纳率: 92.7%
浏览 297

C语言怎么实现这里三角形的计算,怎么取模得到32?

Problem Description
Soda has a complete undirected graph with n vertices. He wants to color the edges with m different colors conveniently labeled from 1 to m. He first selects p edges and colors them. Then he will randomly color the rest edges. He wants to know the total number of different good triangles among all possible graphs.

Let i,j,k (i<j<k) be three vertices in the graph. If there's an edge between i and j, an edge between j and k, an edge between k and i. Then we call the tuple (i,j,k) (i<j<k) is a triangle in the graph. Let the colors for edge (i,j), (j,k), (k,j) be x, y and z. If x≠y and x≠z and y≠z, then we call the triangle good.

Two triangles are considered different if at least one of the six numbers (i,j,k,x,y,z) is different.

Input
There are multiple test cases. The first line of input contains an integer T (1≤T≤100), indicating the number of test cases. For each test case:

The first line contains three integers n, m and p, (3≤n≤100000,1≤m,p≤200000).

Each of the next p lines contains three integer u,v,c (1≤u<v≤n,1≤c≤m) which means the edge (u,v) is colored with color c.

Each edge will be given at most once. Most cases are small.

Output
For each test case, output the total number of good triangles modulo 232.

Sample Input
1
4 6 6
1 2 1
1 3 2
1 4 3
2 3 4
2 4 5
3 4 6

Sample Output
4

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题