题解 P4277 【河城荷取的烟花】

· · 题解

一些前言

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

那次是高一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;
}