けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2386 Sightseeing Tour (JAG 冬合宿 2010 day4-H) (250 点)

AOJ JAG AOJ-ICPC250点 グラフ 数学的帰納法に基づく考察 Greedy:各要素について独立に考えてよい Greedy AOJ-ICPC JAG春冬コン 思わず解きたくなる興味深い良問 トーナメントなど対戦表に関する問題

完全グラフはどのように向きづけしてもハミルトンパスが存在するというね！！！
その証明はすごく楽しいと思う！！！

問題へのリンク

問題概要

頂点数 N の完全無向グラフが与えられる。今、すべての辺に向きをつけたい。各 i, j に対して

  • 頂点 i から頂点 j へと向きをつけるコスト Cij
  • 頂点 j から頂点 i へと向きをつけるコスト Cji

が与えられている。ただし作られる有向グラフにハミルトンパスが存在するようにしたい。そのようなことが可能となる向きづけの最小コストを求めよ。

制約

  • 2 \le N \le 100

考えたこと

実は完全グラフであれば、どのように辺に向きをつけてもハミルトンパスが存在するのだ！！！！！！！！！！

ちなみに向き付きされた完全グラフのことをトーナメントグラフと呼ぶ。

簡単な数学的帰納法で示してみる。結構楽しい証明！！！！！
グラフ楽しい！！！

証明

N 頂点のトーナメントグラフの中から、頂点 v を選び、残りの N-1 頂点について帰納法の仮定からハミルトンパスが存在するので

  • w_{1} → w_{2} → \dots → w_{N-1}

とする。

Case 1

もし v と w_1 を結ぶ辺が、 v から w_1 へ向かう方向に向きづけられているならば、既に v → w_{1} → w_{2} → \dots → w_{N-1} がハミルトンパスである。

Case 2

もし v と w_{N-1} を結ぶ辺が、 w_{N-1} から v へ向かう方向に向きづけられていたならば、既に w_{1} → w_{2} → \dots → w_{N-1} → v がハミルトンパスである。

Case 3

以上のいずれも満たさないとき

  • v と w_1 の関係は w_1 側から
  • v と w_{N-1} の関係は v 側から

という状況になっているが、ということは二分探索的な発想をすることで、ある添字 i が存在して

  • w_i から v への向きに辺がある
  • v から w_{i+1} への向きに辺がある

という風になっているはずである。ちょうど中間値の定理と同じ考え方！！！！！！！

よって w_{1} → w_{2} → \dots → w_{i} → v → w_{i+1} → \dots → w_{N-1} がハミルトンパスになっている。

詰め

本番であれば、以上のような証明は勘で済ませていい気がする。以上のことがわかっていれば

  • 各辺 (i, j) に対して独立に、 C_{i, j} と C_{j, i} のうちの小さい方

を Greedy にとっていけば良い。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N; cin >> N;
    vector<vector<long long> > C(N, vector<long long>(N));
    for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) cin >> C[i][j];  
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            res += min(C[i][j], C[j][i]);
        }
    }
    cout << res << endl;
}