# [Luogu P3288] [BZOJ 3597] [SCOI2014]方伯伯运椰子

xiaoxiao2021-03-01  13

## 题目描述

### 输入输出样例

#### 输入样例#1：

5 10 1 5 13 13 0 412 2 5 30 18 396 148 1 5 33 31 0 39 4 5 22 4 0 786 4 5 13 32 0 561 4 5 3 48 0 460 2 5 32 47 604 258 5 7 44 37 75 164 5 7 34 50 925 441 6 2 26 38 1000 22

103.00

### 说明

1 ≤ N ≤ 5000 , 0 ≤ M ≤ 3000 , 1 ≤ U i , V i ≤ N + 2 , 0 ≤ A i , B i ≤ 500 , 0 ≤ C i ≤ 10000 , 0 ≤ D i ≤ 1000 1\leq N\leq 5000, 0\leq M\leq 3000, 1\leq Ui,Vi\leq N+2, 0\leq Ai,Bi\leq 500, 0\leq Ci\leq 10000, 0\leq Di\leq 1000

### 解题分析

#include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <cctype> #include <cmath> #define R register #define IN inline #define W while #define gc getchar() #define MX 5050 #define db double #define ll long long #define EPS 1e-3 template <class T> IN void in(T &x) { x = 0; R char c = gc; for (; !isdigit(c); c = gc); for (; isdigit(c); c = gc) x = (x << 1) + (x << 3) + c - 48; } int dot, line, cnt; int head[MX]; db dis[MX]; bool vis[MX]; struct Edge {int to, len, nex;} edge[MX << 3]; IN void add(R int from, R int to, R int len) {edge[++cnt] = {to, len, head[from]}, head[from] = cnt;} bool SPFA(R int now, db tar) { vis[now] = true; for (R int i = head[now]; i; i = edge[i].nex) { if(dis[edge[i].to] > dis[now] + edge[i].len + tar) { dis[edge[i].to] = dis[now] + edge[i].len + tar; if(vis[edge[i].to]) return true; if(SPFA(edge[i].to, tar)) return vis[now] = false, true; } } return vis[now] = false; } IN bool check(db tar) { std::memset(vis, false, sizeof(vis)); std::memset(dis, 0, sizeof(dis)); for (R int i = 1; i <= dot; ++i) if(SPFA(i, tar)) return true; return false; } IN void solve() { db lef = 0, rig = 1e8, mid; W(rig - lef > EPS) { mid = (lef + rig) / 2; if(check(mid)) lef = mid; else rig = mid; } printf("%.2lf", mid); } int main(void) { int u, v, a, b, c, d; in(dot), in(line); dot += 2; for (R int i = 1; i <= line; ++i) { in(u), in(v), in(a), in(b), in(c), in(d); if(c) add(v, u, a - d); add(u, v, b + d); } solve(); }