読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

AOJ 2386 - Sightseeing Tour

問題

Sightseeing Tour | Aizu Online Judge

問題概要

はじめ、頂点数Nの完全無向グラフが与えられる。これらの無向辺をすべて、有効辺に置き換えることにした(頂点iと頂点jの間の辺はijjiのどちらかのみが張られる)。そのときのコストがC_{ij}で与えられる。全ての頂点をちょうど一度づつ通るようなパスが存在するようにこの作業を行うときのコストの最小値を求めよ。

イデア

解説を見ながら。

まず、このようにグラフ上の全ての頂点を 1 度ずつ通る路のことを"ハミルトンパス"といい、任意の2点が1つの有向辺で結ばれているグラフを"トーナメント"という名前が付いている。今回、最終的に得られるグラフの形はまさにトーナメントである。

そして、「任意のトーナメントグラフにはハミルトンパスが存在する」。つまり、どのように有向辺を張っても題意を満たすような辺の張り方が可能であるということになる。これを頂点数Nに関する帰納法で示せる。

(証明)

(1) まず、N=1,2のときは明らか。

(2) 次に、N=k( \ge 2)でこれを仮定する。すると、頂点に番号を適当につけることによって12→...→k-1kというようなパスが存在していることになる。そして、頂点k+1と頂点i(1 \le i \le k)の間には、頂点k+1から出ている辺(outと呼ぶ)か、頂点k+1に入っていく辺(inと呼ぶ)のどちらかが存在していることになる。

もし頂点iin、頂点i+1outになっているようなi(1 \le i \le k-1)が存在すれば、既存のルートのii+1の部分をik+1i+1というようにすればよい。

逆に、そのようなiが存在しない時、以下の3通りに場合分け出来る:

  • 全ての頂点がin
  • 全ての頂点がout
  • ある頂点を境界にして、それより前がout、後ろがin(out, out, ..., out, in, ..., inのような形)

この時は単純で、1の状態がoutなら、k+11というパスが既存のルートに加わるだけで、kの状態がinなら、kk+1というパスを既存のルートに加えれば良い。そして以上の3つの場合は、少なくとも一方は満たしているので、このようなパスを作ることが出来る。

よって、N=k+1でも正しい。

(証明終)

これが分かってしまうと後は簡単で、すべての頂点対(i,j)(i \neq j)に対して、C_{ij}C_{ji}の小さい方を選べばよいということになる。

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int n;
    cin >>n;
    int c[100][100];
    rep(i,n)rep(j,n) scanf(" %d", &c[i][j]);

    long ans=0;
    rep(i,n)rep(j,i) ans+=min(c[i][j],c[j][i]);

    printf("%ld\n", ans);
    return 0;
}