新余专业的企业网站建设公司,wordpress 上传 阿里云,wordpress地址站点地址,广州做外贸网站多少钱题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/370/E 来源#xff1a;牛客网
Rinne 喜欢礼物#xff0c;也喜欢送礼物 圣诞节快到了#xff0c;Rinne 要去给给住在城市里的人送礼物 城市的交通可以抽象成一个 n 个点 m 条边的有向图 每条边上有…题干
链接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,m50001≤n≤2000,di≤109,m5000
解题报告 首先可以明确的是如果图不存在环那么肯定无解因为走不回去啊。但是对于这道题可以直接融合在二分中了以为你如果没有环那就ans -1直接就输出 “Rinne is cute” 了
那么我们可以把一种路径的答案表示为 n 表示经过边的数量
考虑枚举答案 ans可以得到判断式通过移项可以得到
那么每次二分这个答案 ans然后把所有的边权都减去 ans找一遍图中有没有负环就可以了。如果有的话说明 ans 还可以更低。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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; in; i) dis[i] INF;for(int i 1; in; i) {for(int j 1; jm; 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; jm; 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; im; i) e[i] ee[i];for(int i 1; im; i) e[i].w - x;bool res bell();//for(int i 1; im; i) e[i].w x;//还原return res;
}int main()
{cinnm;double l 0,r INF;for(int i 1; im; i) {scanf(%d%d%lf,e[i].u,e[i].v,e[i].w);ee[i]e[i];}double mid (lr)/2,ans -1;while(leps r) {mid (lr)/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也对输出lans/2也对就是直接输出ans不对
