首页 > ACM题库 > HDU-杭电 > hdu 2297 Run -模拟退火-[解题报告]C++
2014
01-05

hdu 2297 Run -模拟退火-[解题报告]C++

Run

问题描述 :

Since members of Wuhan University ACM Team are lack of exercise, they plan to participate in a ten-thousand-people Marathon. It is common that the athletes run very fast at first but slow down later on. Start from this moment, we can assume that everyone is moving forward in a constant speed. ACMers love algorithms, so they want to know not only the result but also who may be in the leading position. Now we know all athletes’ position and speed at a specific moment. The problem is, starting from this moment, how many athletes may be the leader. Please notice that there’s no leader if two or more athletes are at the leading position at the same time. No two athletes may have the same speed.

输入:

The input consists of several test cases. The first line of input consists of an integer T, indicating the number of test cases. The first line of each test case consists of an integer N, indicating the number of athletes. Each of the following N lines consists of two integers: p, v, indicating an athlete’s position and speed.

Technical Specification

1. T ≤ 20
2. 0 < N ≤ 50000
3. 0 < p, v ≤ 2000,000,000
4. An athlete’s position is the distant between him/her and the start line.
5. The Marathon is so long that you can assume there’s no finishline.

输出:

The input consists of several test cases. The first line of input consists of an integer T, indicating the number of test cases. The first line of each test case consists of an integer N, indicating the number of athletes. Each of the following N lines consists of two integers: p, v, indicating an athlete’s position and speed.

Technical Specification

1. T ≤ 20
2. 0 < N ≤ 50000
3. 0 < p, v ≤ 2000,000,000
4. An athlete’s position is the distant between him/her and the start line.
5. The Marathon is so long that you can assume there’s no finishline.

样例输入:

1
3
1 1
2 3
3 2

样例输出:

2

转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526      
by—cxlove 

题目:找出一点,距离所有所有点的最短距离最大

http://poj.org/problem?id=1379 

随机化步长,贪心调整即可。

其实用模拟退火需要证明的~~~~%#@&%……@%¥[email protected]

没啥好说的,时限和精度要求都不高,随便搞吧

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<ctime>
#define maxn 200005
#define eps 1e-8
#define inf 2000000000
#define LL long long
#define zero(a) fabs(a)<eps
#define MOD 19901014
#define N 1000005
#define pi acos(-1.0)
using namespace std;
int t,n;
double X,Y;
double best[50];
struct Point{
	double x,y;
	bool check(){
		if(x>-eps&&x<eps+X&&y>-eps&&y<eps+Y)
			return true;
		return false;
	}
}p[1005],tp[50];
double dist(Point p1,Point p2){
	return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double slove(Point p0){
	double ans=inf;
	for(int i=0;i<n;i++)
		ans=min(ans,dist(p[i],p0));
	return ans;
}
int main(){
	scanf("%d",&t);
	srand(time(NULL));
	while(t--){
		scanf("%lf%lf%d",&X,&Y,&n);
		for(int i=0;i<n;i++)
			scanf("%lf%lf",&p[i].x,&p[i].y);
		for(int i=0;i<15;i++){
			tp[i].x=(rand()%1000+1)/1000.0*X;
			tp[i].y=(rand()%1000+1)/1000.0*Y;
			best[i]=slove(tp[i]);
		}
		double step=max(X,Y)/sqrt(1.0*n);
		while(step>1e-3){
			for(int i=0;i<15;i++){
				Point cur,pre=tp[i];
				for(int j=0;j<35;j++){
					double angle=(rand()%1000+1)/1000.0*2*pi;
					cur.x=pre.x+cos(angle)*step;
					cur.y=pre.y+sin(angle)*step;
					if(!cur.check()) continue;
					double tmp=slove(cur);
					if(tmp>best[i]){
						tp[i]=cur;
						best[i]=tmp;
					}
				}
			}
			step*=0.85;
		}
		int idx=0;
		double ans=0;
		for(int i=0;i<15;i++){
			if(best[i]>ans){
				ans=best[i];
				idx=i;
			}
		}
		printf("The safest point is (%.1f, %.1f).\n",tp[idx].x,tp[idx].y);
	}
	return 0;
}

解题转自:http://blog.csdn.net/acm_cxlove/article/details/7954321


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 站长,你好!
    你创办的的网站非常好,为我们学习算法练习编程提供了一个很好的平台,我想给你提个小建议,就是要能把每道题目的难度标出来就好了,这样我们学习起来会有一个循序渐进的过程!

  3. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  4. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。