Codeforces Round #306 (Div. 2) D. Regular Bridge

問題

Problem - D - Codeforces

解法

奇数の場合は写真のようにすれば構成できる。

偶数の場合は作ることは不可能(な気がする)。
あとで証明します。
uwiさんに教えてもらいました。

@mayoko_ まず橋の個数がいくつでも、連結成分をまとめたものは木をなすから、葉が必ずできる。その連結成分について、n頂点だとすると、連結成分のなかの次数の合計はk*n-1になるけど、kが偶数だとこれは奇数になるのでそもそも辺を張れない

— 有為 (@uwitenpen) June 5, 2015

最初の主張(葉が必ずできる,というところ)は「二重辺連結成分分解」というワードで検索するとよくわからない人も納得できると思います。
で,次の主張はグラフ理論でとても基本的な定理「各頂点の次数の和は辺の数の2倍に等しい」という定理から示すことが出来ます。

uwiさん,ありがとうございました。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int k;
    cin >> k;
    if (k % 2 == 0) {
        cout << "NO" << endl;
        return 0;
    }
    vector<pii> ans;
    int n = 2*(2*k-1);
    cout << "YES" << endl;
    for (int i = 1; i < k; i++) {
        ans.push_back(pii(1, 1+i));
    }
    for (int i = 0; i < k-1; i++) {
        for (int j = 0; j < k-1; j++) {
            ans.push_back(pii(2+i, k+1+j));
        }
    }
    for (int i = 0; i < k/2; i++) {
        ans.push_back(pii(k+1+i*2, k+2+i*2));
    }
    ans.push_back(pii(1, k*2));
    for (int i = 1; i < k; i++) {
        ans.push_back(pii(2*k, 2*k+i));
    }
    for (int i = 0; i < k-1; i++) {
        for (int j = 0; j < k-1; j++) {
            ans.push_back(pii(2*k+1+i, 3*k+j));
        }
    }
    for (int i = 0; i < k/2; i++) {
        ans.push_back(pii(3*k+i*2, 3*k+1+i*2));
    }
    cout << n << " " << ans.size() << endl;
    for (auto p : ans) {
        cout << p.first << " " << p.second << endl;
    }
    return 0;
}