“范式杯”2023牛客暑期多校训练营1 - K - Subdivision

Solost

2023 年 07 月 18 日

154 次浏览

暂无评论

1876字数

题目题解

## 题目链接

[链接](https://ac.nowcoder.com/acm/contest/57355/K)

## 题目大意

给你一个无向图，n个点，m条边，你可以在任意一条边中间增加一个点，边的长度还是1，问你从1到各点距离小于等于k的点的个数最多是多少。

## 题解

比赛过程中只想到了这道题的一部分，想着将加点转换成断环和在叶子节点增加儿子，但是在对深度没有印象的边那可以任意加点，不会增加深度

所以正解是，寻找不会影响深度的边，加满。

## 代码

```cpp
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;

vector<int> a[N];

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    vector<int> dist(n + 10, -1), par(n + 10), inner(n + 10);//dist深度，par存放边，用于找出对深度没有影响的边，inner用于记录哪个是树边
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    while(q.size()){
        auto t = q.front();
        q.pop();
        for(auto x : a[t]){
            if(dist[x] != -1) continue;
            q.push(x);
            dist[x] = dist[t] + 1;//计算深度
            par[x] = t;
            inner[t] = 1;//有儿子的节点一定是树边
        }
    }
    ll ans = 1;
    for(int i = 2; i <= n; i++){
        if(dist[i] == -1 || dist[i] > k) continue;
        ll cnt = 0;
        for(auto x : a[i]){
            if(par[x] == i || par[i] == x)//如果这条边被标记过，证明是必须有的
                continue;
            ++cnt;//否则就是对深度没有影响的边
        }
        if(!inner[i])
            cnt = max(cnt, 1ll);//如果不是树边，那就至少可以把自身加满
        ans += (k - dist[i]) * cnt + 1;//+1是指能到达1的都算一个
    }
    cout << ans << endl;
}
int main()
{
    // IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 07 月 18 日