【BZOJ4061】[Cerc2012]Farm and factory（最短路，构造）

题面

BZOJ

然而权限题QwQ。

题解

先求出所有点到达\(1,2\)的最短路，不妨记为\(d_{u,1},d_{u,2}\)。

那么假设新点是\(x\)，任意一个点\(u\)。

那么可以得到几个不等式：\(d_{u,1}\le d_{u,x}+d_{x,1},d_{u,2}\le d_{u,x}+d_{x,2}\)。同理还有几个类似的不等式。

而题目限制又要求\(d_{u,x}\)最小，

因此\(d_{u,x}=max\{|d_{u,1}-d_{x,1}|,|d_{u,2}-d_{x,2}|\}\)

那么把这个东西看成切比雪夫距离，距离某个点切比雪夫距离相等的点是一个正方形，

旋转\(45°\)之后，发现是一个菱形，转成了曼哈顿距离。

而曼哈顿距离两维可以拆开计算，所以只需要对于两维求中位数即可。

详细点吧QwQ，假装要求的是\(max\{|x1-x2|,|y1-y2|\}\)

那么转成\(max\{x1-x2,x2-x1,y1-y2,y2-y1\}\)

令\(x3=x1+y1,y3=x1-y1,x4=x2+y2,y4=x2-y2\)。

那么上面的东西可以变成

\(\frac{1}{2}max\{x3+y3-x4-y4,x4+y4-x3-x4,x3-y3-x4+y4,x4-y4-x3+y3\}\)

化个简就是\(\frac{1}{2}(|x3-x4|+|y3-y4|)\)。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

#define MAXN 100100

#define MAXM 300300

struct Line{int v,next;double w;}e[MAXM<<1];

int h[MAXN],cnt=1;

inline void Add(int u,int v,double w){e[cnt]=(Line){v,h[u],w};h[u]=cnt++;}

double Dis[2][MAXN];

int n,m;

struct Node{int u;double d;};

bool operator<(Node a,Node b){return a.d>b.d;}

priority_queue<Node> Q;bool vis[MAXN];

void Dijkstra(int S,double *dis)

{

	while(!Q.empty())Q.pop();

	for(int i=1;i<=n;++i)vis[i]=false,dis[i]=1e18;

	dis[S]=0;Q.push((Node){S,0});

	while(!Q.empty())

	{

		Node u=Q.top();Q.pop();

		if(vis[u.u])continue;vis[u.u]=true;

		for(int i=h[u.u];i;i=e[i].next)

			if(dis[e[i].v]>dis[u.u]+e[i].w)

			{

				dis[e[i].v]=dis[u.u]+e[i].w;

				Q.push((Node){e[i].v,dis[e[i].v]});

			}

	}

}

double X[MAXN],Y[MAXN];

void Work()

{

	scanf("%d%d",&n,&m);cnt=1;

	for(int i=1;i<=n;++i)h[i]=0;

	for(int i=1;i<=m;++i)

	{

		int u,v;double w;

		scanf("%d%d%lf",&u,&v,&w);

		Add(u,v,w);Add(v,u,w);

	}

	Dijkstra(1,Dis[0]);Dijkstra(2,Dis[1]);

	for(int i=1;i<=n;++i)X[i]=Dis[0][i]+Dis[1][i];

	for(int i=1;i<=n;++i)Y[i]=Dis[0][i]-Dis[1][i];

	sort(&X[1],&X[n+1]);sort(&Y[1],&Y[n+1]);

	double ans=0;

	for(int i=1;i<=n;++i)ans+=fabs(X[i]-X[(n+1)/2]);

	for(int i=1;i<=n;++i)ans+=fabs(Y[i]-Y[(n+1)/2]);

	ans/=2*n;printf("%.10lf\n",ans);

}

int main()

{

	int T;scanf("%d",&T);while(T--)Work();

	return 0;

}