【CCPC-Wannafly Winter Camp Day4 (Div1) J】跑跑跑路（爬山）

点此看题面

大致题意： 共进行两轮游戏，每轮每人有一个标签，标签相同的人必须到同一个点集合。求所有人总路程的最小值。

爬山算法

这道题貌似有三种做法：模拟退火、高斯消元以及爬山算法。

相比之下，自然是爬山算法最简单了。

实现方式

设第一轮编号为\(i\)的节点要到点\(s1_i\)集合，第二轮编号为\(i\)的节点要到点\(s2_i\)集合。

则总答案应为：

\[\sum_{i=1}^n(a_i.x-s1_{f1_i}.x)^2+(a_i.y-s1_{f1_i}.y)^2+(s1_{f1_i}.x-s2_{f2_i}.x)^2+(s1_{f1_i}.y-s2_{f2_i}.y)^2
\]

单独看其中与\(s1_{f1_i}.x\)有关的式子，我们可以发现，要想使这个式子值最小，则\(s1_{f1_i}.x\)与\(a_i.x\)和\(s2_{f2_i}.x\)的差值应越小越好。

但同一个\(s1_{f1_i}.x\)可能会受到多个\(a_i.x\)和\(s2_{f2_i}.x\)影响，所以我们需要使用爬山算法来对其慢慢修正。

具体方式就是每次将\(s1_{f1_i}.x\)减去\(\alpha*(s1_{f1_i}.x-a_i.x)-\alpha*(s1_{f1_i}.x-s2_{f2_i}.x)\)。

其中\(\alpha\)为一个较小的数，可以设为\(10^{-3}\)。

而\(s1_{f1_i}.y,s2_{f2_i}.x,s2_{f2_i}.y\)的修正同理。

代码

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 500

#define DB double

using namespace std;

int n,f1[N+5],f2[N+5];

struct Point

{

	DB x,y;I Point(Con DB& a=0,Con DB& b=0):x(a),y(b){}

	I friend Point operator - (Con Point& x,Con Point& y) {return Point(x.x-y.x,x.y-y.y);}

	I friend Point operator * (Con DB& A,Con Point& x) {return Point(A*x.x,A*x.y);}

}a[N+5];

class FastIO

{

    private:

        #define FS 100000

        #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)

        #define tn(x) (x<<3)+(x<<1)

        #define D isdigit(c=tc())

        int f;char c,*A,*B,FI[FS];

    public:

        I FastIO() {A=B=FI;}

        Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn(x)+(c&15),D);x*=f;}

        Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}

}F;

class ClimbingSolver//爬山算法

{

	private:

		#define Dis2(A,B) (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)//计算题目中所要求的两点间距离的平方

		Point s1[N+5],s2[N+5],s1_[N+5],s2_[N+5];

	public:

		I void Climb()

		{

			RI i,T=50000;Reg DB A=1e-3;W(T--)

			{

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

				{

					s1_[f1[i]]=s1_[f1[i]]-A*(s1[f1[i]]-a[i])-A*(s1[f1[i]]-s2[f2[i]]),//修正s1

					s2_[f2[i]]=s2_[f2[i]]-A*(s2[f2[i]]-s1[f1[i]]);//修正s2

				}for(i=1;i<=n;++i) s1[i]=s1_[i],s2[i]=s2_[i];//复制一遍

			}

		}

		I DB GetAns()//求解

		{

			Reg DB res=0;for(RI i=1;i<=n;++i) res+=Dis2(a[i],s1[f1[i]])+Dis2(s1[f1[i]],s2[f2[i]]);//统计答案

			return res;//返回答案

		}

}C;

int main()

{

	RI i,x,y;for(F.read(n),i=1;i<=n;++i) F.read(x,y),a[i]=Point(x,y);

	for(i=1;i<=n;++i) F.read(f1[i]);for(i=1;i<=n;++i) F.read(f2[i]);//读入

	return C.Climb(),printf("%.10lf",C.GetAns()),0;//求解并输出答案

}

巴特西

【CCPC-Wannafly Winter Camp Day4 (Div1) J】跑跑跑路（爬山）

爬山算法

实现方式

代码

最新文章

热门文章