Combi's blog

By Combi, history, 5 years ago, In English

You are given a binary weighted graph of n vertices and m edges (n <= 100, m <= n * (n — 1) / 2) . Consider all possible spanning tree, its cost is the xor sum of its edges, ans its cost is added to the final answer.

Input:

n m (n <= 100, m <= n * (n - 1) / 2

u v w (1 <= u < v <= n, w is 0 or 1)

Output:

sum of cost of all spanning tree with mod 1e9 + 7

My current approach stops with using Kirchhoff theorem at some point of the problem but I don't know what be the elements of the Laplacian Matrix.

I hope someone will notice and help me to solve this problem.

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I stop at the same point. Can anyone suggest a detailed solution for this problem?