題干：

鏈接：https://ac.nowcoder.com/acm/contest/370/E
來源：牛客網(wǎng)
?

Rinne 喜歡禮物，也喜歡送禮物
圣誕節(jié)快到了，Rinne 要去給給住在城市里的人送禮物
城市的交通可以抽象成一個 n 個點 m 條邊的有向圖
每條邊上有 didi 個居民，Rinne 經(jīng)過這條邊的時候就會給她們每個人都送禮物
由于 Rinne 的禮物并不是很多，她只在城市平均居民數(shù)最少的路上送禮物
Rinne 不想破壞交通規(guī)則，于是她會選擇一個能回到出發(fā)點的路
由于 Rinne 十分可愛，你需要求出這個平均值

輸入描述:

第一個兩個整數(shù) n 和 m 接下來 m 行，每行三個整數(shù) u,v,diu,v,di，表示一條從 u 到 v 居民數(shù)為 didi 的有向道路。

輸出描述:

如果問題無解，也就是 Rinne 找不到一個能回到出發(fā)點的道路，則輸出一行一個字符串`Rinne is cute` 否則，輸出一行一個浮點數(shù)，表示平均損失值最小的回路的平均值大小，輸出保留兩位小數(shù)

示例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

解題報告：

??首先可以明確的是：如果圖不存在環(huán)那么肯定無解（因為走不回去啊）。（但是對于這道題，可以直接融合在二分中了，以為你如果沒有環(huán)，那就ans = -1，直接就輸出 “Rinne is cute” 了）

那么我們可以把一種路徑的答案表示為：（ n 表示經(jīng)過邊的數(shù)量）

考慮枚舉答案 ans，可以得到判斷式，通過移項可以得到

那么每次二分這個答案 ans，然后把所有的邊權(quán)都減去 ans，找一遍圖中有沒有負環(huán)就可以了。如果有的話說明 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;//有負環(huán)}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不對

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 370E】Rinne Loves Gift（Bellman_Ford判负环，二分，分数规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。