本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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)$ 的复杂度做完了本题。

注意事项

1. 题目中并未说明保证图连通，所以可能有多棵基环树，多个环，每个都要统计答案，注意处理。
2. 初始状态 $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;
}

另一种写法

#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;
}

完结撒花！