# [洛谷春令营 D7T4] 天路【二分答案+SPFA判正权环】

• 2018-02-21
• 0
• 0

## Problem:

### 题目描述

“那是一条神奇的天路诶~，把第一个神犇送上天堂~”，XDM先生唱着这首“亲切”的歌曲，一道猥琐题目的灵感在脑中出现了。

```5 6
1 2 1 1
4 1 6 2
5 4 8 1
2 3 2 2
5 2 4 1
3 5 6 4```

`2.3`

## Solution:

• ∑ Vi / ∑ Pi ≤ ans
• ∑ Vi ≤ ans * ∑ Pi
• ∑ Vi - ans * ∑ Pi ≤ 0
• ∑ (Vi  - ans *  Pi) ≤ 0

## Code: O(能过) [2605K, 8MS]

```/*
∑V[i] / ∑P[i] <= ans
=>	∑V[i] <= ans * ∑P[i]
=>	∑(V[i] - ans * P[i]) <= 0
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define eps 1e-3
using namespace std;

inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = num * 10 + ch - '0';
}

int N, M;
int S[20005], T[20005], V[20005], P[20005];

struct Edge{
int np;
double val;
Edge *nxt;
};

struct Graph{
Edge E[20005], *V[7005];
int tope;

inline void clear() {tope = 0, memset(V, 0, sizeof(V));}

inline void addedge(int u, int v, double w){
E[++tope].np = v, E[tope].val = w;
E[tope].nxt = V[u], V[u] = &E[tope];
}
} G;

double dis[7005];
bool inpath[7005];

inline bool dfs_spfa(int u){
inpath[u] = 1;
for(register Edge *ne = G.V[u]; ne; ne = ne->nxt)
if(dis[u] + ne->val > dis[ne->np]){
dis[ne->np] = dis[u] + ne->val;
if(inpath[ne->np]) return 1;
if(dfs_spfa(ne->np)) return 1;
}
return inpath[u] = 0, 0;
}

inline bool check(double k){
G.clear();
for(register int i = 1; i <= M; i++)
G.addedge(S[i], T[i], V[i] - k * P[i]);
memset(dis, 0, sizeof(dis));
memset(inpath, 0, sizeof(inpath));
for(register int i = 1; i <= N; i++)
if(dfs_spfa(i)) return 1;
return 0;
}

int main(){
getint(N), getint(M);
for(register int i = 1; i <= M; i++)
getint(S[i]), getint(T[i]), getint(V[i]), getint(P[i]);
double l = 0.0, r = 200.0;
while(l + eps < r){
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
if(l < eps) puts("-1");
else printf("%.1f\n", l);
return 0;
}
```

#### 评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai