• 欢迎光临~

【CF1253F】Cheap Robot(最小生成树,最短路)

开发技术 开发技术 2022-10-28 次浏览

首先发现所有询问点都是充电桩这个条件很有用。

它能滋生出一种暴力到极端的想法:用 Floyd 对全局跑一遍最短路。然后新建一个图,图中两两充电桩连一条边,边权为它们之间的最短路,代表着从这个充电桩直接走到那个充电桩最少要备多少电。然后再把新图的最小生成树建出来,询问时直接询问树上两点路径边权最大值。

发现时间压根过不去,也不太好直接优化。

发现瓶颈主要是在跑 Floyd (O(n^3)) 和建图 (O(k^2)),这是我们我们远远不能接受的。

但是原图最多也就 (m) 条边,所以上面的做法只能把时间复杂化。

于是考虑能不能直接在题目给的原图上搞东西。

于是就有了一种神奇的思路:

既然充电桩直接两两建边我们不能接受,我们不如直接枚举 (c),把两个距离 (leq c) 的充电桩之间连一条边,然后再看题目询问的 (A)(B) 充电桩在什么时候联通。

但是枚举 (c) 貌似也要跟充电桩两两间的距离有关,那怎么转移到原图上的边呢?

在原图上,我们先用 dijkstra 预处理出每一个点 (i) 到离它最近的充电桩的距离 (dis_i)。然后设当前枚举的为 (c)

然后对于原图中的每一条边 ((u,v)),设其边权为 (w)。如果 (dis_u+w+dis_vleq c),,那么就连上边 ((u,v)),然后再判断 (A)(B) 在原图中是否联通。

为什么这样做是对的呢?(以下的 (A)(B) 均代表任意两个充电桩)

  1. ((u,v)) 被连上,那么 (u)(v) 的最近充电桩间的距离 (leq c)

    证明显然,根据 ((u,v)) 被连上的条件的定义即可得出。

  2. (A)(B) 的距离 (leq c),那么 (A)(B) 联通。

    如果两个充电桩 (A)(B) 的距离 (leq c),那么这样做之后他们一定联通。因为对于 (A)(B) 最短路上的每一条边 ((u,v)),它肯定能满足 (dis_u+w+dis_vleq c),因为这个式子代表着从离 (u) 最近的充电桩出发、能经过 ((u,v)) 走到离 (v) 最近的充电桩且满足路程 (leq c),而从 (A) 走到 (B) 肯定算入一种方案,所以 ((u,v)) 这条边肯定能连上。

  3. 推广到间接联通上,如果 (A)(B) 联通,(A) 就真的能到达 (B) 吗?

    答案是肯定的,因为 (A)(B) 的联通路径上的每一条边都被连上,那么根据上述两点证明,可以得出这条边的两个端点的最近充电桩可以互相到达,而 (A) 可以通过这些能互相到达的充电桩直接或间接地到达 (B)

所以这样做是正确的。

至于维护连边的过程,我们可以用并查集。

同时我们可以把询问离线下来,在并查集的每个联通块内记录这个连通块内包含的未解决询问,而合并连通块时要用启发式合并才能保证时间复杂度,具体详见代码。

然后枚举 (c) 实在是太大了,不然直接先把每条边按 (dis_u+w+dis_v) 排序,再依次枚举边。

这样你就发现这种 “给边排序,再依次加入图中判断联通” 的方法和 kruskal 类似,只不过边权改了一下而已,而且还带上了询问。

具体代码如下:

#include<bits/stdc++.h>

#define N 100010
#define M 300010
#define ll long long

using namespace std;

struct Edge
{
	int u,v;
	ll w;
}e[M];

struct Query
{
	int a,b;
	ll ans;
	Query(){ans=-1;}
}q[M];

struct data
{
	int u;
	ll s;
	data(){};
	data(int a,ll b){u=a,s=b;}
	bool operator < (const data &a) const
	{
		return s>a.s;
	}
};

int n,m,k,Q;
int fa[N];
int cnt,head[N],nxt[M<<1],to[M<<1],w[M<<1];
ll dis[N];

vector<int>g[N];
priority_queue<data>que;

void adde(int u,int v,int wi)
{
	to[++cnt]=v;
	w[cnt]=wi;
	nxt[cnt]=head[u];
	head[u]=cnt;
}

void dijkstra()
{
	memset(dis,127,sizeof(dis));
	for(int i=1;i<=k;i++)
		que.push(data(i,0)),dis[i]=0;
	while(!que.empty())
	{
		data now=que.top();
		que.pop();
		for(int i=head[now.u];i;i=nxt[i])
		{
			int v=to[i];
			if(dis[now.u]+w[i]<=dis[v])
			{
				dis[v]=dis[now.u]+w[i];
				que.push(data(v,dis[v]));
			}
		}
	}
}

bool cmp(Edge a,Edge b)
{
	return a.w<b.w;
}

int find(int x)
{
	return x==fa[x]?x:(fa[x]=find(fa[x]));
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&Q);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%lld",&e[i].u,&e[i].v,&e[i].w);
		adde(e[i].u,e[i].v,e[i].w),adde(e[i].v,e[i].u,e[i].w);
	}
	for(int i=1;i<=Q;i++)
	{
		scanf("%d%d",&q[i].a,&q[i].b);
		g[q[i].a].push_back(i),g[q[i].b].push_back(i);
	}
	dijkstra();
	for(int i=1;i<=m;i++)
		e[i].w=e[i].w+dis[e[i].u]+dis[e[i].v];
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int a=find(e[i].u),b=find(e[i].v);
		if(a!=b)
		{
			if(g[b].size()<g[a].size()) swap(a,b);//注意启发式合并的size比较不是比较的并查集的size而是询问大小的size
			fa[a]=b;
			for(int j=0,size=g[a].size();j<size;j++)
			{
				int x=find(q[g[a][j]].a),y=find(q[g[a][j]].b);
				if(x==y)
				{
					if(q[g[a][j]].ans==-1)
						q[g[a][j]].ans=e[i].w;
				}
				else g[b].push_back(g[a][j]);
			}
		}
	}
	for(int i=1;i<=Q;i++)
		printf("%lldn",q[i].ans);
	return 0;
}
程序员灯塔
转载请注明原文链接:【CF1253F】Cheap Robot(最小生成树,最短路)
喜欢 (0)