题解：P6890 [CEOI 2006] Link

Handezheng · 2025-03-20 19:54:31 · 题解

题解：P6890 [CEOI 2006] Link

题目传送门

题面

给定 n 个点 n 条有向边的内向基环树（不保证连通），要求添加最少的有向边使得点 1 到达所有其它点的最短路长度不超过 K。

思路

首先考虑到内向基环树就是带着一个环的 DAG，所以如果有某个点入度为 0，肯定要从 1 向它连边。

先把不是环上的点处理好，令 f_i 表示从 i 点还能走多少步满足性质，能够得到转移方程 f_v = \max{f_v,f_u-1}，并且发现，若 f_u=0，一定要从 1 向它连边，可用拓扑处理。

对于环上的点，我们可以先扩散一遍，得到的 f_u 实质上就是从 u 点能跳到哪个点；对于所有的 f_u=0，必须连边并统计贡献。设环上有 L 个点，能够得到单次查询的时间复杂度为 O(\frac L k)。

正常情况下我们要以环上的每一个满足 f_u=0 点为起点进行跳跃，时间复杂度 O(\frac {L^2} k)。但是我们注意到，在这些满足条件的点中，每 k 个就成一次循环，它们的决策实质上是一样的，所以我们可以只进行 k 次查询，时间复杂度为 O(\frac {L^2} k \times k)=O(L)。这样我们就以 O(n) 的复杂度做完了本题。

注意事项

题目中并未说明保证图连通，所以可能有多棵基环树，多个环，每个都要统计答案，注意处理。

初始状态 f_1=k+1，不要忘记。

代码


#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define int long long
#define F(i,l,r) for(int i=(l); i<=(r); i++)
using namespace std;
const int N = 1e6 + 50, INF=0x3f3f3f3f3f3f3f3f;

int n,K,cnt; int ind[N], f[N]; int to[N];

inline void Topsort(){ queue<int> q; F(i,1,n) if(!ind[i]){ q.push(i); f[i] = K; cnt+=(i!=1); } f[1]=K+1; for(; q.size(); q.pop()){ int u=q.front(), v=to[u]; if(!f[u])cnt++, f[u]=K; f[v]=max(f[v],f[u]-1); ind[v]--; if(!ind[v]) q.push(v); } } inline int fun(int rt, int tot, int cir[]){ int sum=0, res=0; for(int i=rt; sum<tot;){ int u=cir[i]; if(f[u]){ sum+=f[u]; i = (i+f[u]-1)%tot + 1; }else{ res++; sum+=K; i = (i+K-1)%tot +1; } } return res; }

signed main(){ ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);

cin>>n>>K;
F(i,1,n){
    int u,v; cin>>u>>v;
    to[u]=v;
    ind[v]++;
}
Topsort();
F(i,1,n){
    if(ind[i]){
        vector<int> vec;

        for(int u=i,v; ind[u]; u=v){
            ind[u]=0;
            vec.push_back(u);
            v=to[u];
            f[v]=max(f[v],f[u]-1);
        }

        int cir[vec.size()+3]={0}, tot=0, Cnt=0, mi=INF;
        for(int e:vec) cir[++tot]=e;
        F(j,1,tot){
            if(f[cir[j]]) continue ;
            Cnt++;
            mi = min(mi, fun(j,tot,cir));
            if(Cnt==K) break;
        }
        cnt+=(mi==INF)?0:mi;
    }
}
cout<<cnt<<'\n';

return 0;

}

另一种写法
```cpp
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define int long long
#define F(i,l,r) for(int i=(l); i<=(r); i++)
using namespace std;
const int N = 1e6 + 50, INF=0x3f3f3f3f3f3f3f3f;

int n,K,cnt;
int ind[N], f[N];
int cir[N],tot;
int to[N];

inline void Topsort(){
    queue<int> q;
    F(i,1,n) if(!ind[i]){
        q.push(i);
        f[i] = K;
        cnt+=(i!=1);
    }
    f[1]=K+1;
    for(; q.size(); q.pop()){
        int u=q.front(), v=to[u];
        if(!f[u])cnt++, f[u]=K;
        f[v]=max(f[v],f[u]-1);
        ind[v]--;
        if(!ind[v]) q.push(v);
    }
}
inline int fun(int rt){
    int sum=0, res=0;
    for(int i=rt; sum<tot;){
        int u=cir[i];
        if(f[u]){
            sum+=f[u];
            i = (i+f[u]-1)%tot + 1;
        }else{
            res++;
            sum+=K;
            i = (i+K-1)%tot +1;
        }
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n>>K;
    F(i,1,n){
        int u,v; cin>>u>>v;
        to[u]=v;
        ind[v]++;
    }
    Topsort();
    F(i,1,n){
        if(ind[i]){
            tot=0;
            for(int u=i,v; ind[u]; u=v){
                ind[u]=0;
                cir[++tot]=u;
                v=to[u];
                f[v]=max(f[v],f[u]-1);
            }

            int Cnt=0, mi=INF;
            F(j,1,tot){
                if(f[cir[j]]) continue ;
                Cnt++;
                mi = min(mi, fun(j));
                if(Cnt==K) break;
            }
            cnt+=(mi==INF)?0:mi;
        }
    }
    cout<<cnt<<'\n';

    return 0;
}

完结撒花！