自动搬运

查看原文

来自洛谷，原作者为

	Ireliaღ 逝去的是刀锋，不变的是意志

搬运于2025-08-24 21:58:26，当前版本为作者最后更新于2019-12-17 08:37:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一些前言

这道题对于我们机房有着里程碑一样的意义，因为它让我们最能抄题解最菜的那只当场退役。

那次是高一NOIP之后不久的一次模拟赛，考了三道题，这个是T3，考完之后大部分人前两题拿了大部分分，T3爆零，那兄弟前两题爆零，T3切了，后来教练发现是copy的Solution，他就退役了。

（本来想放个我们学校OJ的截图，但是他被我们教练从OJ里踢了，表格里没有他了。

解题思路

考虑把大的问题逐步分解

首先我们整体解题框架就是枚举所有可以点燃的点作为方案，对于每一个方案，算出所有绳子被燃尽的时间的最大值，求出这些最大值的最小值就是答案。

那么当我们确定了点燃点时，如何确定每根绳子被燃尽的时间？

为了方便存储，我们把一根绳子从中间折半分成两根存储。我们以拆完后所有的绳子端点为节点，以每根绳子燃烧时间为边权建图。显然，从$s$点燃的话，每一个节点$i$被燃到的时间点就是$s$开始的单源最短路。这样，我们就求出了所有端点的被点燃的时间。

已知绳子两端点的点燃时间和燃烧速度，如何求出绳子燃尽时间？显然是小学相遇问题，大家都会推。

这样这个问题就被完美解决了。

程序实现

这道题的思路很巧，并且程序实现细节较多，大家可以看代码注释。

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cstring>
//防CE+防抄袭 
#define x1 partychicken
#define x2 vcode
#define y1 ubospica
#define y2 greygoods

using namespace std;
const int MAXN = 2005;
const double EPS = 1e-6;
const double INF = 1e9;

int n, m;
int id[4005][4005];//如果坐标(i, j)是绳子端点，那么建的图中的节点为id[i][j] 
int cant[MAXN];//绳子折半后中间点不能作为开始点，在这标一下 
int to[MAXN], nxt[MAXN], head[MAXN], ecnt;
double val[MAXN], dis[MAXN];
int lid[MAXN], rid[MAXN], tot;//每根绳子两端点对应图中的节点编号 
double v[MAXN];//每根绳子燃烧速度 
double ans;

void Add(int u, int v, double w) {
	to[++ecnt] = v; val[ecnt] = w; nxt[ecnt] = head[u]; head[u] = ecnt;
	to[++ecnt] = u; val[ecnt] = w; nxt[ecnt] = head[v]; head[v] = ecnt;
//	cerr << u << ' ' << v << ' ' << w << '\n';
}

void SetStick(int x1, int y1, int x2, int y2, double len) {
	x1 <<= 1; x1 += 2001;//为了便于计算，把坐标调整调正 
	y1 <<= 1; y1 += 2001;
	x2 <<= 1; x2 += 2001;
	y2 <<= 1; y2 += 2001;
	int x3 = (x1 + x2 >> 1), y3 = (y1 + y2 >> 1);//中间点 
	if (!id[x1][y1]) id[x1][y1] = ++n;//在图中建出节点 
	if (!id[x2][y2]) id[x2][y2] = ++n;
	if (!id[x3][y3]) id[x3][y3] = ++n;
	cant[id[x3][y3]] = 1;//中间点不能点燃 
	Add(id[x1][y1], id[x3][y3], len / 2.0);
	Add(id[x3][y3], id[x2][y2], len / 2.0);
	lid[++tot] = id[x1][y1]; rid[tot] = id[x3][y3]; v[tot] = 1.0 / len;//记录每条边的信息 
	lid[++tot] = id[x3][y3]; rid[tot] = id[x2][y2]; v[tot] = 1.0 / len;
}

int q[MAXN], ql, qr;
int vis[MAXN];

void SPFA(int s) {//单源最短路 
	for (int i = 1; i <= n; i++) dis[i] = INF; dis[s] = 0;
	ql = qr = 1; q[1] = s;
	memset(vis, 0, sizeof(vis)); vis[s] = 1;
	while (ql <= qr) {
		int u = q[ql++ % n]; vis[u] = 0;
		for (int i = head[u]; i; i = nxt[i]) {
			int v = to[i];
			if (dis[v] - dis[u] > val[i] + EPS) {
				dis[v] = dis[u] + val[i];
				if (!vis[v]) {
					vis[v] = 1;
					q[++qr % n] = v;
				}
			}
		}
	}
//	cerr << '*';
//	for (int i = 1; i <= n; i++) cerr << dis[i] << ' ';
//	cerr << '\n';
}

double EndTime(int sid) {//相遇问题，计算绳子被燃尽的时间 
	double t1 = dis[lid[sid]], t2 = dis[rid[sid]], V = v[sid];
	if (t1 - t2 > EPS) swap(t1, t2);
	if (t2 - t1 > 0.5 / V) return t1 + 0.5 / V;
	double res1 = t2;
	double res2 = (0.5 - V * (t2 - t1)) / (V * 2.0);
	return res1 + res2;
}

void Cal(int s) {//计算从节点s点燃，所有绳子被燃尽的时间 
	SPFA(s);
	double res = 0;
	for (int i = 1; i <= tot; i++) res = max(res, EndTime(i));
	ans = min(ans, res);//更新总答案 
}

int main() {
	cin >> m;
	for (int i = 1; i <= m; i++) {
		int x1, y1, x2, y2; double t;
		cin >> x1 >> y1 >> x2 >> y2 >> t;
		SetStick(x1, y1, x2, y2, t);
	}
	ans = INF;
	for (int i = 1; i <= n; i++) {//枚举点燃点 
		if (cant[i]) continue;
		Cal(i);
	}
	cout << fixed << setprecision(4) << ans << '\n';
	return 0;
}