POJ 3687 - Labeling Balls
Problem : There are n balls with weight 1~n. Now label them with number 1~n, and meet some constraints { (weight(label a)<weight(label b) }. Output the sequence weight(label 1), weight(label 2), ..., weight(label n). If multiple answer exist, output the lexicographical smallest one.
Solution : 1. For each (weight(label a)<weight(label b)), add an edge from b to a. If there's no cycle, answer exists. 2. If answer exists, Assign weight N->1 to the lexicographical largest topological order in the label DAG.
Proof :
1.
<- : If there is a cycle, a path from a->a exists, which means weight(a)>weight(a). Contradiction.
-> : If no cycle, the graph is DAG. Then any topological order label is valid, since if there is a constraint weight(a)>weight(b), a comes before b in topological order, thus it get the larger weight ball.
2.
For the current graph with k vertices, there is a vertice u with largest label number and with no previous vertice, and v is another vertice without previous vertice. Assign weight k to u is always get better answer than v, because,
	A. If u get the weight k, then weight(u)>weight(v) ( There remains weight 1~k-1 for remaining vertices ).
	B. Let A2 to be a solution for the condition v get the weight k, and let weight(u)=k'. By reduce the weight of vertice with weight from k'+1 to k by 1, and assign k to u, The assignation is still valid, but optimizer than before. (valid proof) Since for each edge (i->j) in current graph, either weight(i)-weight(j)>1 or weight of j is reduced by 1 if that of i is reduced.
In total, the method is equal with the largest lexicographical topological order of label DAG.
[]