ABC197 F - Construct a Palindrome - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

${N}$ 頂点 ${M}$ 辺の連結無向グラフの各辺に英小文字が ${1}$ つ書かれている．頂点 ${1}$ から頂点 ${N}$ までのウォークのうち，通った辺に書かれた文字を順に並べると回文となるようなものの回文の長さの最小値を求めよ．

${2\leq N \leq 1000\\ 1\leq M\leq 1000}$

解説

回文の性質(というか定義)と，始点・終点が固定という条件からいろいろ考えてみると， ${1\rightarrow N}$ が回文になっているなら ${1\rightarrow v}$ と ${N\rightarrow v}$ が等しいような頂点 ${v}$ が存在するか， ${1\rightarrow u}$ と ${N\rightarrow v}$ が等しいような隣接する頂点 ${u,v}$ が存在する，ということがわかる(逆も言える)．

頂点 ${1}$ と頂点 ${N}$ から同じ文字が書かれた辺を，上の条件を満たすまで辿ればとりあえず回文になる．

同時に辿って行くのは難しいので，二つの頂点を( ${(1,N)}$ のように)一つの頂点にまとめるようなグラフを作ることで，同じ文字が書かれた辺の対ごとに新たなグラフに辺を張ればいい．

例：元のグラフで ${a,b}$ 間の辺と ${c,d}$ 間の辺に書かれた文字が同じ場合，新たなグラフでは ${(a,c),(b,d)}$ 間， ${(a,d),(b,c)}$ 間に辺を張る．

元のグラフで ${a}$ から ${b}$ に， ${c}$ から ${d}$ に行くことは新たなグラフで ${(a,c)}$ から ${(b,d)}$ に行くことに対応する．
同様に，元のグラフで ${a}$ から ${b}$ に， ${d}$ から ${c}$ に行くことは新たなグラフで ${(a,d)}$ から ${(b,c)}$ に行くことに対応する．

このようなグラフでの ${(1,N)}$ から ${(v,v)}$ や ${(u,v)}$ ( ${u,v}$ は隣接する) までの最短距離を求める問題になる．同じ文字が書かれた辺の対に張られた辺(例の ${(a,c),(b,d)}$ 間など)のコストを ${2}$ ，新たに頂点 ${G}$ を作り， ${(v,v)}$ から ${G}$ にコスト ${0}$ の辺を張り， ${(v,u)}$ から ${G}$ にコスト ${1}$ の辺を張ることで， ${(1,N)}$ から ${G}$ への最短コストが答えとなる．

提出プログラム

感想

連結って条件いる？アルファベットサイズも関係なさそう．