AOJ 3047 - Shiritori
解法
ある文字が最後の1文字となるには、ある文字が先頭となっている単語をすべて使い切った上で、その文字が最後の文字となっている単語にいきつくことが必要になります。
a～zまでの文字をそれぞれ頂点としたグラフを考えます。すべての単語は、先頭の文字から最後の文字への有向辺になります。辺の重みをすべて1と考えると、先頭の文字から最後の文字への辺が複数あることは、その数だけの重みがある辺が1つ存在することと同じです(apple、ateという2つの単語が存在したときに、aからeへの重みが2の辺が存在する、といった具合です)。
このときに、ある文字xが最後の1文字となるには、文字xが先頭の単語を最初に選ぶと1単語分お得になります。なので、xが先頭の単語から始めることにします。
こうしたときに、xが先頭の単語の数だけ、最後の文字がxの単語に行きつかないといけないので、
- xからxの最大流が、xから流すことができるフローと等しい
という条件を満たす必要があります。
xから流すことができるフローは、入力の時点で先頭の文字をチェックしていくことで調べることができるので、あとは最大流を求めることができれば答えを求めることができます。
xからxへの最大流を調べるには、xを流す側と流れる側の頂点に分割します。
すべての文字について調べたいので、全ての頂点を、始点と終点に分割しておきます。ここで気を付けるべきなのが、終点から始点へは好きなだけフローを流せるようにしておく、ということです。でないと、全ての頂点を分割しているために、フローが途中で途切れてしまいます。
あとは、頂点数を2倍にして組み立てたグラフを使い、最大流を調べていくことで答えを求めることができます。
