#P17861. [XV Open Cup]Potential Well
[XV Open Cup]Potential Well
题目描述
给定一个有 个顶点、 条边的有向带权图。你需要为每个顶点 选择一个实数势能 。
对于一条从 到 、原权值为 的边,重赋权后的权值为
图的强度定义为所有重赋权后的边权中的最小值:
$$S=\min_{(u,v,w)\in E}\bigl(w-\varphi(v)+\varphi(u)\bigr).$$请最大化图的强度。如果强度没有有限的上界,输出 +inf;否则输出最大强度和一组达到该值的势能。
输入格式
第一行包含两个整数 。
接下来 行,每行包含三个整数 ,表示一条从 到 、权值为 的有向边。
图不保证连通,权值可以为负。不要假定不存在自环或重边。
输出格式
如果答案无上界,只输出一行 +inf。
否则,第一行输出一个实数 ,第二行输出 个实数 。
每个势能的绝对值不得超过 。输出的 与正确最大强度的绝对误差,以及输出的 与按你输出的势能计算出的实际强度的绝对误差,都必须不超过 。请输出足够的小数位。NaN 和无穷大等非有限数值不合法。
数据范围
- ;
- ;
- ;
- 。
样例 1
3 3
1 2 1
2 3 1
3 1 1
1.0
0.0 0.0 0.0
样例 2
2 1
1 2 1
+inf