How to calculate the state of a graph?
- by zcb
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?