late_riser's blog

By late_riser, 9 years ago, In English

[EDIT] It is Codeforces Round — 270, not SRM-270. Sorry for mixing up with TopCoder!

My understanding of the problem as below: A matrix is given where each entry (row,col) represents weight of an edge from row to col. We have to check if the matrix can be represented as a weighted tree.

So, I think, there are two things to check. If a node has a positive edge (weight>0) to itself, then it is not a weighted tree. If weight[u,v] != weight[v,u], then it is also not a weighted tree.

Are these conditions sufficient? I think NO. But, I am not getting what else should we check. I googled about "weighted tree" to gain some knowledge. I found that it is a tree simply weights are given for every edge. Am I missing something?

If anyone can clarify the problem description and the missing parts of my knowledge about weighted tree, I will be grateful!

Thanks!

  • Vote: I like it
  • -8
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

There are only 3 problems in SRM. What problem do you mean?

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

You misunderstood the problem.Given matrix entities don't represent the weight of edge from row to col. It represents the weight of PATH from row to col.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, it can be said a path. Whatever you say it (path or edge), it is a "connection" (with weight) between parent child of a tree, right?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, there is connection.But not all such weights can't be the distance-matrix of a weighted tree. Example : 0 2 5 3 2 0 3 5 5 3 0 2 3 5 2 0 But, this will form : 0 2 5 3 2 0 3 5 5 3 0 8 3 5 8 0 The point is some values will imply others.And take two vertices i and k.which has an edge between them. For all other vertices u, dist[i][u] will be dist[i][k]+dist[k][u] or dist[k][u] will be dist[k][i]+dist[i][u]. These properties won't be satisfied in any general graph.