[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!
There are only 3 problems in SRM. What problem do you mean?
When I participated, I got a list of 7 problems as this list. Problem D is this problem
I think he means "Codeforces Round #270"
@Los_Angelos_Laycurse: Yes, thats what I mean. I edited the title. Thanks for your understanding. :)
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.
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?
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.