#423 Div2 D

题意

构造一个 n 个节点的树，恰好有 k 个叶子节点 (叶子节点的定义是只与树上的某一个节点存在连边)，要求任意两个叶子节点的距离的最大值最小，距离为两个节点间边的数量，输出距离的最大值，以及 n - 1 条边。

分析

构造 “星型树” ，节点 1 为中心，首先连 k 条边到 k 个节点，对于多的点，周期性的绕最外层的 k 个点不断连接即可。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 5;

typedef pair<int, int> P;

vector<P> ans;

vector<int> v1, v2;

int main() {

    int n, k;

    cin >> n >> k;

    n--;

    n -= k;

    int lens = 2;

    for(int i = 2; i <= k + 1; i++) {

        ans.push_back(P(1, i));

        v1.push_back(i);

    }

    int z = k + 2;

    while(n) {

        lens++;

        if(n > 1) lens++;

        for(int i = 0; i < v1.size() && n > 0; i++) {

            ans.push_back(P(v1[i], z));

            v2.push_back(z);

            z++; n--;

        }

        v1.clear();

        v1 = v2;

        v2.clear();

    }

    cout << lens << endl;

    for(int i = 0; i < ans.size(); i++) {

        cout << ans[i].first << " " << ans[i].second << endl;

    }

    return 0;

}

巴特西

#423 Div2 D

#423 Div2 D

题意

分析

code

最新文章

热门文章