HackerRank savita-and-friends

Description

在一条边上求一个点,使得这个点到所有点的最长的最短距离最短. \(n \leqslant 10^5\)

Sol

Dijkstra+扫描线+单调队列.

这个好像叫什么最小直径生成树?不过变成了在一个边上...

对于一个点,我们可以求出当分割点在哪个位置的时候,它应该到 \(A\) ,什么时候它应该到 \(B\) .

\(dis_A(i)+t \leqslant dis_B(j)+(dis_{AB}-t)\)

移项得 \(t\leqslant \frac{dis_B(i)-dis_A(i)+dis_{AB}}{2}\)

这样就把线段 \(AB\) 分成了几个区间,枚举区间,然后分别用两个单调队列维护一下到分割点左右到 \(A,B\) 距离的最大值.

对于一个区间,我们可以 \(O(1)\) 的求出在这个区间应该选择哪个点作为分割点,因为两边的点都是确定的最大距离也知道,然后统计答案就可以了.

Code

#include<cstdio>

#include<cstring>

#include<vector>

#include<queue>

#include<algorithm>

#include<functional>

#include<iostream>

using namespace std;

#define mpr(a,b) make_pair(a,b)

#define debug(a) cout<<#a<<"="<<a<<" "

#define Fst first

#define Sec second

typedef long long LL;

typedef pair< LL,int > pr;

const int N = 100005;

LL T,n,m,k,A,B,X;

vector<pr> g[N];

LL ds[N],dt[N];

pair< double,int > p[N];double lm[N];

pair< double,double > ans;

int q1[N],q2[N],h1,h2,t1,t2;

priority_queue<pr,vector<pr>,greater<pr> > q;

inline LL in(LL x=0,char ch=getchar()){ while(ch>'9' || ch<'0') ch=getchar();

	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x; }

void clr(){

	t1=t2=0,h1=h2=1;ans=mpr(1e18,-1);

	for(int i=0;i<N;i++) g[i].clear();

}

void Up(int i,int j){

	double l=max(min((X+ds[j]+dt[i])/2.0-ds[j],lm[j]),lm[i]),tmp=max(ds[j]+l,X-l+dt[i]);

//	debug(i),debug(j),debug(dt[i]),debug(ds[j]),debug((X+ds[j]+dt[i])/2.0-dt[i]),debug(lm[i]),debug(lm[j]),debug(l),debug(tmp)<<endl;

	if(tmp < ans.Fst||(tmp == ans.Fst && l<ans.Sec)) ans=mpr(tmp,l);

}

void Dijkstra(int s,LL *d){

	static bool b[N];memset(b,0,sizeof(b));for(int i=1;i<=n;i++) d[i]=1000000000000000000LL;

	d[s]=0,q.push(mpr(0,s));

	for(int u;!q.empty();){

		u=q.top().Sec,q.pop();if(b[u]) continue;b[u]=1;

		for(int i=0;i<g[u].size();i++){

			LL p=g[u][i].Fst;int v=g[u][i].Sec;

			if(d[u]+p < d[v]) d[v]=d[u]+p,q.push(mpr(d[v],v));

		}

	}

}

int main(){

	for(T=in();T--;){

		clr();

		n=in(),m=in(),k=in();

		for(int i=1,u,v,x;i<=m;i++){

			u=in(),v=in(),x=in();

			g[u].push_back(mpr(x,v)),g[v].push_back(mpr(x,u));

			if(i == k) A=u,B=v,X=x;

		}

		Dijkstra(A,ds),Dijkstra(B,dt);

//		cout<<X<<endl;

//		for(int i=1;i<=n;i++) cout<<ds[i]<<" ";cout<<endl;

//		for(int i=1;i<=n;i++) cout<<dt[i]<<" ";cout<<endl;

		for(int i=1;i<=n;i++) p[i]=mpr((dt[i]-ds[i]+X)/2.0,i),lm[i]=(dt[i]-ds[i]+X)/2.0;

		sort(p+1,p+n+1);

//		for(int i=1;i<=n;i++) printf("%lf %d\n",p[i].Fst,p[i].Sec);

		for(int i=1;i<=n;i++){

			while(h2<=t2 && ds[q2[t2]] <= ds[p[i].Sec]) t2--;

			q2[++t2]=p[i].Sec;

		}

//		cout<<ds[q2[h2]]+X<<endl;

		ans=mpr(ds[q2[h2]],0);

		for(int i=1,r;i<=n;i=r+1){

			r=i;

			while(p[r].Fst == p[r+1].Fst) r++;

///			debug(r)<<endl;

			for(int j=i;j<=r;j++){ while(h1<=t1 && dt[q1[t1]] <= dt[p[j].Sec]) t1--;q1[++t1]=p[j].Sec; }

			for(int j=i;j<=r;j++) if(q2[h2] == p[j].Sec) h2++;

//			debug(q1[h1]),debug(q2[h2])<<endl;

			Up(q1[h1],q2[h2]);

		}

		if(dt[q1[h1]]<ans.Fst) ans=mpr(dt[q1[h1]],X);

		printf("%.5lf %.5lf\n",ans.Sec,ans.Fst);

	}

	return 0;

}

巴特西

HackerRank savita-and-friends

Description

Sol

Code

最新文章

热门文章