#P17861. [XV Open Cup]Potential Well

[XV Open Cup]Potential Well

题目描述

给定一个有 nn 个顶点、mm 条边的有向带权图。你需要为每个顶点 vv 选择一个实数势能 φ(v)\varphi(v)。

对于一条从 uu 到 vv、原权值为 ww 的边,重赋权后的权值为

w′=w−φ(v)+φ(u).w'=w-\varphi(v)+\varphi(u).

图的强度定义为所有重赋权后的边权中的最小值:

$$S=\min_{(u,v,w)\in E}\bigl(w-\varphi(v)+\varphi(u)\bigr).$$

请最大化图的强度。如果强度没有有限的上界,输出 +inf;否则输出最大强度和一组达到该值的势能。

输入格式

第一行包含两个整数 n,mn,m。

接下来 mm 行,每行包含三个整数 ui,vi,wiu_i,v_i,w_i,表示一条从 uiu_i 到 viv_i、权值为 wiw_i 的有向边。

图不保证连通,权值可以为负。不要假定不存在自环或重边。

输出格式

如果答案无上界,只输出一行 +inf。

否则,第一行输出一个实数 SS,第二行输出 nn 个实数 φ(1),φ(2),…,φ(n)\varphi(1),\varphi(2),\ldots,\varphi(n)。

每个势能的绝对值不得超过 101010^{10}。输出的 SS 与正确最大强度的绝对误差,以及输出的 SS 与按你输出的势能计算出的实际强度的绝对误差,都必须不超过 10−510^{-5}。请输出足够的小数位。NaN 和无穷大等非有限数值不合法。

数据范围

  • 2≤n≤10002\le n\le1000;
  • 1≤m≤1000001\le m\le100000;
  • 1≤ui,vi≤n1\le u_i,v_i\le n;
  • ∣wi∣≤106|w_i|\le10^6。

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