自动搬运

查看原文

来自洛谷，原作者为

	pocafup 路 是人走出来的

搬运于2025-08-24 22:20:46，当前版本为作者最后更新于2020-04-09 01:57:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题外话：

EZEC官方题解：

有点桑心啊。。。这次除了内部人员居然没人AC这题，搞了好久的说。

唯一一个35分的代码还是写的无优化LCA解法，而且他思路我还没看懂

被吐槽除了算法之外有点裸，这里讲一下：这题原本的想法其实是后面讲到的正解第二种（虽然当时没有想到tarjan），但是原本的思路并没有第一种正解那么裸

---

对于 $N \le 10$ 的数据，实时记录小E和PF到每个岛的距离，然后 $dfs$ 枚举每种可能的走法。复杂度 $N!$。

---

对于 $N \le 16$ 的数据，考虑状压dp。$dp[i][j]$ 记录当前的状态以及当前所在的点。状压完后对每个状态进行统计。如果状态数超过 $l$ 并且小于当前所能得到的最小值 ，那么就更新答案。

在状压过程中更新答案会更快但这个跟正解没啥关系。

复杂度为 $n*2^n$，可以过。

代码略（状压你都会你跟我讲你想不出正解？）

---

当数字变大后，指数级别的答案肯定不合法。因此，我们需要一个更快的方法。

第一步观察到狱长的最短距离在加边前后都是一个固定值（未必相等）。因此，我们可以预处理这个距离，加边，然后再预处理一次。

可以发现，由于只有 $N-1$ 条边，在加边之前每一条边到另一条边都有唯一的最短路。

在 $N\le500$ 的数据时，我们可以对每个点跑一次 $dij$，预处理出每个点到其他任意点的距离和长度，再进行加边操作。狱长只能加一次边的操作我们可以使用分层图来实现。

加完边后，暴力枚举 $K$，取最大的 $K$ 作为答案。

暴力枚举的部分代码：

//maxi为最大的p_i和e_i的值
inline void find_ans(){
  int ans1=-1,ans2;
  for (int i=1;i<=maxi;i++){
    int re = dijk(1,i);
    if(re>=L) ans1 = i,ans2 = re;
  }
  if (ans1==-1) cout << "no solution";
  else cout << ans1 << endl << ans2;
}

这个算法复杂度为 $N^2 \times Max(p_i,e_i)$，大约为 $500^3$，可以在规定时间内跑完。

另一种方法为保留到每条边的最小 $K$ 值，预处理后对整张图统计一次最小答案，这里留给读者自行思考。

---

当 $N \le2500$ 的时候，我们需要一个更加简单的方法。

我们可以发现，既然每两点只有一条边互通，那么他们只有一个公共祖先。他们之间的最短距离可以表示为两点分别到公共祖先的距离的和，他们之间的点的数量可以表示为两个点的深度减去祖先的深度。这个操作可以使用 $LCA$ 来实现。

因此，我们只需要从点 $1$ 开始跑一个 $dij$ ，然后对于每两点判断一下是否能够加边。

加完边后，我们可以二分 $K$，如果小 E 能够跑到 $L$ 个点上，并且到每个点的距离都比狱长小，那么这个 $K$ 是可实现的。

这个做法的复杂度为 $N^2logN$ ，可以过 $N \le 2500$ 的数据

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>
#include <math.h>
using namespace std;
const int MAXN = 5e3+5;
#define pp pair<long long,long long>
#define f first
#define s second
const int BD = 14;
int n,m,t,L,q,d,level[MAXN<<1],pa[MAXN<<1][BD];
inline long long read() {
  long long x=0,w=1;
  char ch;
  while(ch<'0'||ch>'9'){
    if(ch=='-') w=-1;
    ch=getchar();
  }
  while(ch>='0'&&ch<='9')
  x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
  return x*w;
}
bool inq[MAXN<<1];
vector<pp> adj[MAXN<<1],adj2[MAXN<<1];
long long dist1[MAXN<<1],dist2[MAXN<<1],dist3[MAXN];
int LCA(int u, int v) {
	if(level[u] < level[v]) swap(u,v);
	int diff = level[u] - level[v];
	for(int i=0; i<BD; i++) if((diff>>i)&1 ) u = pa[u][i];
	if(u == v) return u;
	for(int i=BD-1; i>=0; i--) if(pa[u][i] != pa[v][i]) {
		u = pa[u][i];
		v = pa[v][i];
	}
	return pa[u][0];
}//找LCA的板子
void set_up_lca(int nn){
  for(int i = 1 ; i <= BD ; i++){
    for(int j = 0; j < nn ; j++){
      if(pa[j][i-1] != -1) pa[j][i] = pa[pa[j][i-1]][i-1] ;
    }
  }
}//lca的板子
void dfs(int pos, int lev, int prev){
  pa[pos][0] = prev;
  level[pos] = lev;
  for (pp v : adj[pos]){
    if (v.f==prev) continue;
    dfs(v.f,lev+1,pos);
  }
}//把深度找出来
inline void dij(int source, vector<pp> adja[MAXN], long long dist[MAXN]){
  for (int i=0;i<=2*n;i++) dist[i] = 1e9;
  queue<int> q;
  dist[source] = t;
  q.push(source);
  while(!q.empty()){
    long long qs = q.front(); q.pop();
    inq[qs] = false;
    for (pp v : adja[qs]){
      if (dist[v.f]>dist[qs]+v.s){
        dist[v.f]=dist[qs]+v.s;
        if (!inq[v.f]) inq[v.f] = true,q.push(v.f);
      }
    }
  }
}//预处理距离
inline void add_edge(){
  for (int i=1;i<=n;i++){
    for (int j=i+1;j<=n;j++){
      if(i==j)continue;
      int lca = LCA(i,j);
      long long dis = dist2[i]+dist2[j]-2*dist2[lca];
      if (dis<=d && level[i]+level[j]-2*level[lca]-1>=q){//如果他们距离小于D且之间有超过Q个点
        adj2[i].push_back(make_pair(j+n,floor(dis/2)));
        adj2[j].push_back(make_pair(i+n,floor(dis/2)));
      }
    }
  }
}
bool seem[MAXN];
inline int dijk(int source, long long num){
  memset(dist1,0x3f3f3f,sizeof(dist1));
  memset(seem,0,sizeof(seem));
  queue<int> q;
  int re = 0;
  dist1[source] = 0;
  q.push(source);
  while(!q.empty()){
    long long qs = q.front(); q.pop();
    inq[qs] = false;
    if (!seem[qs]) seem[qs] = true,re++;
    for (pp v : adj[qs]){
      if (v.s>num) continue;//如果这条边的距离用K足够
      if (dist1[v.f]>dist1[qs]+v.s && dist1[qs]+v.s<=dist3[v.f]){//如果
        dist1[v.f]=dist1[qs]+v.s;
        if (!inq[v.f])inq[v.f] = true,q.push(v.f);
      }
    }
  }
  return re;
}
inline void bs(){
  long long l = 0, r = 1e18;
  while(l!=r-1){
    long long mid = (l+r)/2;
    if (dijk(1,mid)>=L) r = mid;
    else l = mid;
  }//二分
  if (dijk(1,l)>=L) cout << l << endl << dijk(1,l);
  else if (dijk(1,r)>=L) cout << r << endl << dijk(1,r);
  else cout << "no solution";
}
inline void update_dis(){
  for (int i=1;i<=n;i++) dist3[i] = min(dist2[i],dist2[i+n]);
}

int u,v,p,e;
int main(){
  n = read(); t= read(); d = read(); L = read();q = read();
  for (int i=0;i<n-1;i++){
    u = read(); v = read(); p = read(); e = read();
    adj[u].push_back(make_pair(v,p));
    adj[v].push_back(make_pair(u,p));
    adj[u+n].push_back(make_pair(v+n,p));
    adj[v+n].push_back(make_pair(u+n,p));
    adj2[u].push_back(make_pair(v,e));
    adj2[u+n].push_back(make_pair(v+n ,e));
    adj2[v].push_back(make_pair(u,e));
    adj2[v+n].push_back(make_pair(u+n ,e));//别忘了双向边和分层图边的加法
  }
  for (int i=1;i<(MAXN<<1);i++){
    for (int j=0;j<BD;j++){
      pa[i][j] = -1;
    }
  }
  dfs(1,0,-1);
  set_up_lca(n*2);//预处理公共祖先
  dij(1,adj2,dist2);//预处理距离
  add_edge();//加边
  dij(1,adj2,dist2);//再预处理距离
  update_dis();//更新距离
  bs();//二分
}

另一种更简单的思维方法是暴力枚举节点进行 $dijkstra$ ，这里留给读者自行思考

---

当 $N\le 7500$ 的时候，$N^2logN$ 会直接被卡掉。

这时候，我们需要一个更简便的方法。

这时候，万能的 $dfs$ 就出来了。

暴力枚举每个节点，顺着边往下走。当距离超过 $D$ 时就返回，否则如果中间岛屿超过 $Q$ 就加边。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include <math.h>
using namespace std;
#define G() Cr=getchar()
#define LL long long
LL Xr,Fr;char Cr;
int bian;
inline LL rd(){
	Xr=0,Fr=1;G();
	while(Cr<'0'||Cr>'9'){if(Cr=='-')Fr=-1;G();}
	while(Cr>='0'&&Cr<='9')Xr=(Xr<<1)+(Xr<<3)+Cr-'0',G();
	return Xr*Fr;
}
#define MAX_N 15000
#define MAX_M 10000000
#define oo 9999999999999999
int n, T, D, L, Q;
LL dis[MAX_N], Dis[MAX_N];
LL va[MAX_N], Va[MAX_M];
int to[MAX_N], ne[MAX_N], he[MAX_N], cnt;
int To[MAX_M], Ne[MAX_M], He[MAX_M], Cnt;
int add_u[MAX_M], add_v[MAX_M], add_t;
LL add_d[MAX_M];
int a, b;
LL c, d;
bool vis[MAX_N];
LL ans, Ans, Ma, num;

void add(int u, int v){
	to[++cnt]=v;
	ne[cnt]=he[u];
	he[u]=cnt;
	va[cnt]=c;
}

void Add(int u, int v){
	To[++Cnt]=v;
	Ne[Cnt]=He[u];
	He[u]=Cnt;
	Va[Cnt]=d;
}

void dfs_ae(int U, int u, LL dd, int t, int la){
	if(dd>D)return;
	if(t>=Q) add_u[++add_t]=U, add_v[add_t]=u, add_d[add_t]=floor(dd/2);
	for(int i=He[u];i;i=Ne[i]) if(To[i]!=la && To[i]<=n) dfs_ae(U,To[i],dd+Va[i],t+1,u);
}//预处理

void Dijk(int U){
	priority_queue< pair<int,int> >q;
	q.push(make_pair(0,U));
	for(int i=1;i<=2*n;i++) Dis[i]=oo;
	Dis[U]=0;
	while(!q.empty()){
		int u=q.top().second;
		if (-q.top().first>Dis[u]) {q.pop(); continue;}
		q.pop();
		vis[u]=1;
		for(int i=He[u];i;i=Ne[i]){
			int v=To[i];
			if(vis[v])continue;
			if(Dis[v]>Dis[u]+Va[i]){//跟之前同样的操作
				Dis[v]=Dis[u]+Va[i];
				q.push(make_pair(-Dis[v],v));
			}
		}
	}
}
bool seem[MAX_N];
void dijk(int t){
	memset(seem,0,sizeof(seem));
	priority_queue< pair<int,int> >q;
	q.push(make_pair(0,1));
	for(int i=1;i<=n;i++) dis[i]=oo, vis[i]=0;
	dis[1]=0;
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		num++;
		seem[u] = true;
		for(int i=he[u];i;i=ne[i]){
			int v=to[i];
			if(seem[v])continue;
			if(dis[v]>dis[u]+va[i] && dis[u]+va[i]<=T+Dis[v] && va[i]<=t){
				dis[v]=dis[u]+va[i];
				q.push(make_pair(-dis[v],v));
			}
		}
	}
}

bool check(int t){
	num=0;
	dijk(t);
	if(num>=L){
		Ans=num;
		return 1;
	}
	else return 0;
}//某数字是否能实现

int main(){
	cin>>n>>T>>D>>L>>Q;
	for(int i=1;i<n;i++){
		a=rd(), b=rd(), c=rd(), d=rd();
		Ma=max(Ma,c);
		if(c) add(a,b), add(b,a);
		if(d) Add(a,b), Add(b,a), Add(a+n,b+n), Add(b+n,a+n);
	}
	for(int i=1;i<=n;i++) dfs_ae(i,i,0,-1,0);//预处理狱长距离
	for(int i=1;i<=add_t;i++) {
		d=add_d[i], Add(add_u[i],add_v[i]+n);}//加边
	Dijk(1);//二次处理
	for(int i=1;i<=n;i++)Dis[i]=min(Dis[i],Dis[i+n]);//更新距离
	ans=2147483647;
	int l=0, r=Ma;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)) ans=mid, r=mid-1;
		else l=mid+1;
	}//二分套路
	if(ans==2147483647)puts("no solution");
	else cout<<ans<<endl<<Ans;
}

正解其实并不比75分做法难想。然而，这题有一个玄学的地方：

void dfs_ae(int U, int u, LL dd, int t, int la){
	if(dd>D)return;
	if(t>=Q) add_u[++add_t]=U, add_v[add_t]=u, add_d[add_t]=floor(dd/2);//这行
	for(int i=He[u];i;i=Ne[i]) if(To[i]!=la && To[i]<=n) dfs_ae(U,To[i],dd+Va[i],t+1,u);
}

看起来确实像是多此一举。貌似还多开了一个数组。

然而，如果将这里改成这样:

void dfs_ae(int U, int u, LL dd, int t, int la){
	if(dd>D)return;
	d = floor(dd/2);
	Add(U,u);
	// if(t>=Q) add_u[++add_t]=U, add_v[add_t]=u, add_d[add_t]=floor(dd/2);
	for(int i=He[u];i;i=Ne[i]) if(To[i]!=la && To[i]<=n) dfs_ae(U,To[i],dd+Va[i],t+1,u);
}

就会惊奇的发现获得了70分的成绩。虽然总复杂度不变，但是如此建边有一个特点：每次 dfs 边加边，会导致所有边都被枚举了一次，最后复杂度可能变为 $O(N(N+M))$ ， $M$ 为加边条数，导致时间复杂度爆炸。

这种解法复杂度为 $N^2$，能够在规定时间跑完。

---

另一种较为复杂的方法为 $LCA$ $+$ $tarjan$ 。我们可以发现，如果从树的顶端往下跑，那么当某两个点在同一棵树内，他们的祖先的祖先对他没有任何意义。同理，如果从下往上跑，那么子树对于父节点也没有任何意义。于是，当我们处理完子树，我们可以直接合并子树的祖先。（其实只能说类似tarjan）

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <fstream>
#include <cstring>
#include <math.h>
using namespace std;
const int MAXN = 7e3+505;
#define pp pair<long long,long long>
#define f first
#define s second
const int BD = 12;
const int MAXB = 10000000;
int n,m,t,L,q,ed,d,level[MAXN<<1];
inline long long read() {
	long long x=0,w=1;
	char ch;
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*w;
}
struct Edge{
  int t,d,nxt;
}edge[MAXB],edge2[MAXB];
int head[MAXN],head2[MAXN<<1],tot,tot2;
inline void add(int from, int to, int dis){
  edge[++tot].t = to;
  edge[tot].d = dis;
  edge[tot].nxt = head[from];
  head[from] = tot;
}
inline void add2(int from, int to, int dis){
  edge2[++tot2].t = to;
  edge2[tot2].d = dis;
  edge2[tot2].nxt = head2[from];
  head2[from] = tot2;
}
bool inq[MAXN<<1];
long long dist1[MAXN],dist2[MAXN<<1],dist3[MAXN];
void dfs(int pos, int lev, int prev){
	level[pos] = lev;
	for(int i = head[pos];i;i=edge[i].nxt){
    int to =edge[i].t;
		if (to==prev) continue;
		dfs(to,lev+1,pos);
	}//同样写lca的配方
}
inline void dij(int source){
  fill(dist2+1,dist2+1+2*n,1e18);
	queue<int> q;
	dist2[source] = t;
	q.push(source);
	while(!q.empty()){
		long long qs = q.front(); q.pop();
		inq[qs] = false;
    for (int i=head2[qs];i;i=edge2[i].nxt){
      int to = edge2[i].t,d = edge2[i].d;
      if (dist2[to]>dist2[qs]+d){
        dist2[to]=dist2[qs]+d;
        if (!inq[to])inq[to] = true,q.push(to);
      }
    }
	}
}//还是同样的方法
int father[MAXN];
int LCA(int x){
	return father[x]^x?father[x]=LCA(father[x]):x;
}//lca的方法
int bian = 0;
bool visit[MAXN];
inline void add_edge(int i,int fa){
	father[i]=i;
	for(int j=head2[i];j;j=edge2[j].nxt){
    int to = edge2[j].t;
		if(to^fa && !visit[to]){
			add_edge(to,i);
			father[to]=i;
		}//先建子树,然后合并
	}
	visit[i]=true;
	for (int j=1;j<=n;j++){
		if(i==j || !visit[j])continue;
		int lca = LCA(j);
		long long dis = dist2[i]+dist2[j]-(dist2[lca]<<1);
		if (dis<=d && level[i]+level[j]-(level[lca]<<1)-1>=q){
			bian+=2;
      add2(i,j+n,dis/2);
      add2(j,i+n,dis/2);
		}
	}//建边
}
bool seem[MAXN];
inline int dijk(int source, long long num){
	memset(dist1,0x3f3f3f,sizeof(dist1));
	memset(seem,0,sizeof(seem));
	queue<int> q;
	int re = 0;
	dist1[source] = 0;
	q.push(source);
	while(!q.empty()){
		long long qs = q.front(); q.pop();
		inq[qs] = false;
		if (!seem[qs]) seem[qs] = true,re++;
		for(int i = head[qs];i;i=edge[i].nxt){
      int to = edge[i].t,d = edge[i].d;
			if (d>num) continue;
			if (dist1[to]>dist1[qs]+d && dist1[qs]+d<=dist3[to]){
				dist1[to]=dist1[qs]+d;
				if (!inq[to])inq[to] = true,q.push(to);
			}
		}
	}
	return re;
}//二分dij
inline void bs(){
	long long l = 0, r = 1e18;
	while(l!=r-1){
		long long mid = (l+r)/2;
		if (dijk(1,mid)>=L) r = mid;
		else l = mid;
	}
	if (dijk(1,l)>=L) cout << l << endl << dijk(1,l);
	else if (dijk(1,r)>=L) cout << r << endl << dijk(1,r);
	else cout << "no solution";
}//二分
inline void update_dis(){
	for (int i=1;i<=n;i++) dist3[i] = min(dist2[i],dist2[i+n]);
}//更新
int u,v,p,e;
int main(){
	n = read(); t= read(); d = read(); L = read();q = read();
	ed = n;
	for (int i=0;i<n-1;i++){
		u = read(); v = read(); p = read(); e = read();
    add(u,v,p);
    add(v,u,p);
    add2(u,v,e);
    add2(v,u,e);
    add2(u+n,v+n,e);
    add2(v+n,u+n,e);
	}
	dfs(1,0,-1);
	dij(1);
	add_edge(1,-1);
	dij(1);
	update_dis();
	bs();//这里方法基本与上面一样
}

---

部分分方法：

对于 $Q=0$ 的点，我们可以直接两两判断时间是否超越 $D$，并不需要判断之间的距离。期望得分 $35$，实际得分 $45$。

对于不加边的做法，我们就不加边，不使用分层图，预计得分 $20$，实际得分 $20$。

---

对于大常数选手（比如我），我们给与了足够大的空间和时间（ $2$ 倍空间时间）。但由于要卡 $75$ 分做法，如果正解常数巨大的话无法满分。