【BFS树】“范式杯”2023牛客暑期多校训练营1 K

蔚落 2024-03-17 21:30 75阅读 0赞

[K-Subdivision\_“范式杯”2023牛客暑期多校训练营1 (nowcoder.com)][K-Subdivision_2023_1 _nowcoder.com]

题意：

![4a0823d41e2441abb413bac96c6b8828.png][]

思路：

![0b33a4e30c7f436ebd23759ea188f516.jpeg][]

首先对1结点进行BFS，形成一棵BFS树

贡献由两部分组成

第一部分由BFS树的非树边组成

第二部分由树边组成

对于第一部分，对于一个结点和该结点相邻的非树边上产生的有效结点数最多为 K-dis\[u\]

该结点可能会有很多条非树边，因此要先统计该结点非树边的个数cnt

对于这个结点产生的所有非树边，产生的贡献为(K-dis\[u\])\*cnt+1

最后的+1是算上它本身

对于第二部分，有一个结论就是，把结点加在叶子结点对应的边上最优

证明如下：

![fa9e67af02f2433aa73209685153337a.png][]

因此我们对每个叶子结点去算贡献

对于一个叶子结点，贡献也为(K-dis\[u\])\*cnt+1

只不过对于叶子结点，有贡献的边至少为1，因此需要cnt=max(cnt,1)

样例解释：

![b92619163b2d43eaae04ffc4aa64b5e2.jpeg][]

其余的在代码中给出了解释：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxe=1e5+10;
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    int N,M,K,u,v;
    int tot=0;
    int head[mxn],dis[mxn],inner[mxn],pre[mxn];
    
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void bfs(){
        memset(dis,-1,sizeof(dis));
        queue<int> Q;
        Q.push(1);
        dis[1]=0;
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            for(int i=head[u];~i;i=edge[i].next){
                if(dis[edge[i].to]==-1){
                    dis[edge[i].to]=dis[u]+1;
                    pre[edge[i].to]=u;//判断是否为非树边
                    inner[u]=1;//标记是否是BFS树的叶子结点
                    Q.push(edge[i].to);
                }
            }
        }
    }
    void solve(){
        cin>>N>>M>>K;
        G_init();
        for(int i=1;i<=M;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        bfs();//建立BFS树
        int ans=1;//算上1结点
        for(int u=2;u<=N;u++){
            if(dis[u]==-1||dis[u]>K) continue;//对于不在BFS树上的点，或者在树上离1结点太远的点，都没有贡献
            int cnt=0;
            for(int i=head[u];~i;i=edge[i].next){
                if(pre[edge[i].to]==u||pre[u]==edge[i].to) continue;//判断是否为非树边
                cnt++;//统计有效边，对于非树边那就是非树边的个数
            }
            if(!inner[u]) cnt=max(cnt,1ll);//如果为叶子结点，有效边至少为1，就是叶子结点对应的那条边
            ans+=(K-dis[u])*cnt+1;//计算贡献
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[K-Subdivision_2023_1 _nowcoder.com]: https://ac.nowcoder.com/acm/contest/57355/K
[4a0823d41e2441abb413bac96c6b8828.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d663589b013e4e51b277ed79d6eae35a.png
[0b33a4e30c7f436ebd23759ea188f516.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/02b31a3598eb495c9a7004e9f35746f6.png
[fa9e67af02f2433aa73209685153337a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/44b146ff177f4375bb4efbe5d3f776a1.png
[b92619163b2d43eaae04ffc4aa64b5e2.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/d4e2a352233a4d1ab2b706f19a8955f1.png