Spanning Trees [CSAcademy #54]

https://csacademy.com/contest/round-54/task/spanning-trees/

整数N,Kがある。
以下の条件をグラフを構築せよ。

• N頂点の辺重み付け無向グラフ
• 最大全域木と最小全域木がユニークに存在
• 最大全域木と最小全域木で共通に使われている辺がK本ある
• 多重辺無し、自己辺無し
• 辺の数は最大2N
• コストは1～10^9
• 作れないなら"-1"

K＜N≦10^5

解法

まず、特殊な場合を考える。

• N=1
  • 辺が張られないので、辺を張らないのが答え。
• K=0かつ(N=1またはN=2)
  • この場合は作れないので"-1"

　
それ以外は作れるが、K=0と0＜Kで挙動が違うので、分けて考える。
　

• K=0
  • 最小全域木(辺のコスト1)
    • 0-1-2-3-...-(N-1)と辺を張る
  • 最大全域木(辺のコスト2)
    • (N-1)と0～(N-3)と辺を張る
    • 0と(N-2)に辺を張る

• 0＜K
  • 共有な辺(辺のコスト2)
    • 0-1-2-...-Kと辺を張る
  • 最小全域木(辺のコスト1)
    • 0と(K+1)～(N-1)に辺を張る
  • 最大全域木(辺のコスト3)
    • 1と(K+1)～(N-1)に辺を張る

using T = tuple<int, int, int>;
int N, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    vector<T> ans;
    if (K == 0) {
        if (N == 1) {
            printf("0\n");
            return;
        }

        if (N == 2 or N == 3) {
            printf("-1\n");
            return;
        }

        rep(i, 0, N - 1) ans.push_back(T(i, i + 1, 1));
        rep(i, 0, N - 2) ans.push_back(T(i, N - 1, 2));
        ans.push_back(T(0, N - 2, 2));
    } else {
        rep(i, 0, K) ans.push_back(T(i, i + 1, 2));
        rep(i, K + 1, N) ans.push_back(T(0, i, 1));
        rep(i, K + 1, N) ans.push_back(T(1, i, 3));
    }

    int n = ans.size();
    printf("%d\n", n);
    fore(t, ans) {
        int a, b, c;
        tie(a, b, c) = t;
        printf("%d %d %d\n", a + 1, b + 1, c);
    }
}