Блог пользователя Combi

Автор Combi, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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