题干：
链接：https://ac.nowcoder.com/acm/contest/370/E
来源：牛客网
Rinne 喜欢礼物，也喜欢送礼物
圣诞节快到了，Rinne 要去给给住在城市里的人送礼物
城市的交通可以抽象成一个 n 个点 m 条边的有向图
每条边上有 didi 个居民，Rinne 经过这条边的时候就会给她们每个人都送礼物
由于 Rinne 的礼物并不是很多，她只在城市平均居民数最少的路上送礼物
Rinne 不想破坏交通规则，于是她会选择一个能回到出发点的路
由于 Rinne 十分可爱，你需要求出这个平均值
输入描述:
第一个两个整数 n 和 m
接下来 m 行，每行三个整数 u,v,diu,v,di，表示一条从 u 到 v 居民数为 didi 的有向道路。
输出描述:
如果问题无解，也就是 Rinne 找不到一个能回到出发点的道路，则输出一行一个字符串`Rinne is cute`
否则，输出一行一个浮点数，表示平均损失值最小的回路的平均值大小，输出保留两位小数 示例1
输入
2 2
1 2 2
2 1 3 输出
2.50 示例2
输入
2 1
1 2 1 输出
Rinne is cute 备注:
1≤n≤2000,di≤109,m<=50001≤n≤2000,di≤109,m<=5000 解题报告：
首先可以明确的是：如果图不存在环那么肯定无解（因为走不回去啊）。（但是对于这道题，可以直接融合在二分中了，以为你如果没有环，那就ans = -1，直接就输出 “Rinne is cute” 了）
那么我们可以把一种路径的答案表示为：
考虑枚举答案 ans，可以得到判断式
那么每次二分这个答案 ans，然后把所有的边权都减去 ans，找一遍图中有没有负环就可以了。如果有的话说明 ans 还可以更低。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
const int MAX = 2e5 + 5;
const double eps = 1e-4;
const double INF = 1e9 + 2333;
int n,m;
double dis[MAX];
struct Edge {
int u,v;
double w;
} e[MAX],ee[MAX];
bool bell() {
for(int i = 1; i<=n; i++) dis[i] = INF;
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=m; j++) {
if(dis[e[j].u] + e[j].w < dis[e[j].v]) {
dis[e[j].v] = dis[e[j].u] + e[j].w;
}
}
}
for(int j = 1; j<=m; j++) {
if(dis[e[j].u] + e[j].w < dis[e[j].v]) return 1;//有负环
}
return 0 ;
}
bool ok(double x) {
for(int i = 1; i<=m; i++) e[i] = ee[i];
for(int i = 1; i<=m; i++) e[i].w -= x;
bool res = bell();
//for(int i = 1; i<=m; i++) e[i].w += x;//还原
return res;
}
int main()
{
cin>>n>>m;
double l = 0,r = INF;
for(int i = 1; i<=m; i++) {
scanf("%d%d%lf",&e[i].u,&e[i].v,&e[i].w);
ee[i]=e[i];
}
double mid = (l+r)/2,ans = -1;
while(l+eps < r) {
mid = (l+r)/2;
if(ok(mid)) r = mid,ans = mid;
else l = mid;
}
if(ans < 0) printf("Rinne is cute\n");
else printf("%.2lf\n",ans-eps);
return 0 ;
} 最后这个答案输出l也对，输出（l+ans）/2也对，，就是直接输出ans不对
京公网安备 11010502036488号