問題

問題概要

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

アイデア

解説を見ながら。

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

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

(証明)

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

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

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

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

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

この時は単純で、 $1$ の状態がoutなら、 $k+1$ → $1$ というパスが既存のルートに加わるだけで、 $k$ の状態がinなら、 $k$ → $k+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;
}

裏紙

ほぼ競プロ、たまに日記

AOJ 2386 - Sightseeing Tour

問題

問題概要

アイデア

実装(C++)