# algorithm problem: Prove minimum ring division on directed graph can be solved in polynomial time

Given a directed graph $G\langle V,E\rangle$, and weight $w[u][v]$ of each $\langle u,v \rangle$ representing an edge of $E$ the question is, try to divide the whole graph into several "rings", making each vertex $u$ belong to a certain "ring" and a "ring" contains at least two vertices, it's guaranteed that the given graph must be able to be divided, satisfying the restrictions.

Finally, please make the total weight of all the "ring"s minimum .

This is a task assigned by my tutor, I don't know if it's an old problem because I'm new on algorithm, my tutor told me that it could be solved within polynomial time complexity, I wanna know how it can be done, I just have no idea about that...

PS: I'm terribly sorry for my forgetting to post the correct question at the first time...

-
Your title says 'minimum', but your statement of the problem doesn't. (Nor does it use the weights w[u][v].) Please clarify! – TonyK Dec 23 '10 at 19:18
What exactly do you mean by ring? – Mariano Suárez-Alvarez Dec 24 '10 at 14:39
I assume 'rings' means 'disjoint cycles'. – TonyK Dec 24 '10 at 15:12