How to calculate the state of a graph?
Posted
by
zcb
on Stack Overflow
See other posts from Stack Overflow
or by zcb
Published on 2012-10-14T03:05:20Z
Indexed on
2012/10/14
3:37 UTC
Read the original article
Hit count: 147
Given a graph G=(V,E), each node i is associated with 'Ci' number of objects. At each step, for every node i, the Ci objects will be taken away by the neighbors of i equally. After K steps, output the number of objects of the top five nodes which has the most objects.
Some Constrains: |V|<10^5, |E|<2*10^5, K<10^7, Ci<1000
My current idea is: represent the transformation in each step with a matrix. This problem is converted to the calculation of the power of matrix. But this solution is much too slow considering |V| can be 10^5.
Is there any faster way to do it?
© Stack Overflow or respective owner