Two Longest Paths (UVa 11823)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=226&page=show_problem&problem=2923

問題

DAGがある。ノードが重複しないように取った2つのパスを考える。その2つのパスで使用したノードの合計の最大値を求めよ。ただし、パスに含まれるノードが一つの場合でもパスとみなす。
1<=ノードの数<=300
1<=辺の数<=3000

解法

最小費用流で解く。