裸题，第二个权值是自己点的个数。二分之后用spfa判负环就行了。
题目描述
考虑带权的有向图G=(V,E)G=(V,E)G=(V,E)以及w:E→Rw:E\rightarrow Rw:E→R,每条边e=(i,j)(i≠j,i∈V,j∈V)e=(i,j)(i\neq j,i\in V,j\in V)e=(i,j)(i≠j,i∈V,j∈V)的权值定义为wi,jw_{i,j}wi,j，令n=∣V∣n=|V|n=∣V∣。c=(c1,c2,⋯,ck)(ci∈V)c=(c_1,c_2,\cdots,c_k)(c_i\in V)c=(c1,c2,⋯,ck)(ci∈V)是GGG中的一个圈当且仅当(ci,ci+1)(1≤i<k)(c_i,c_{i+1})(1\le i<k)(ci,ci+1)(1≤i<k)和(ck,c1)(c_k,c_1)(ck,c1)都在EEE中，这时称kkk为圈ccc的长度同时令ck+1=c1c_{k+1}=c_1ck+1=c1，并定义圈c=(c1,c2,⋯,ck)c=(c_1,c_2,\cdots,c_k)c=(c1,c2,⋯,ck)的平均值为μ(c)=∑i=1kwci,ci+1/k\mu(c)=\sum\limits_{i=1}^{k} w_{c_i,c_{i+1}}/kμ(c)=i=1∑kwci,ci+1/k，即ccc上所有边的权值的平均值。令μ′(c)=Min(μ(c))\mu'(c)=Min(\mu(c))μ′(c)=Min(μ(c))为GGG中所有圈ccc的平均值的最小值。现在的目标是：在给定了一个图G=(V,E)G=(V,E)G=(V,E)以及w:E→Rw:E\rightarrow Rw:E→R之后，请求出GGG中所有圈ccc的平均值的最小值μ′(c)=Min(μ(c))\mu'(c)=Min(\mu(c))μ′(c)=Min(μ(c))
输入输出格式
输入格式：
第一行2个正整数，分别为nnn和mmm，并用一个空格隔开，只用n=∣V∣,m=∣E∣n=|V|,m=|E|n=∣V∣,m=∣E∣分别表示图中有nnn个点mmm条边。 接下来m行，每行3个数i,j,wi,ji,j,w_{i,j}i,j,wi,j，表示有一条边(i,j)(i,j)(i,j)且该边的权值为wi,jw_{i,j}wi,j。输入数据保证图G=(V,E)G=(V,E)G=(V,E)连通，存在圈且有一个点能到达其他所有点。
输出格式：
请输出一个实数μ′(c)=Min(μ(c))\mu'(c)=Min(\mu(c))μ′(c)=Min(μ(c))，要求输出到小数点后8位。
题干：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<ctime>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define duke(i,a,n) for(register int i = a;i <= n;++i)
#define lv(i,a,n) for(register int i = a;i >= n;--i)
#define clean(a) memset(a,0,sizeof(a))
const int INF = 1 << 30;
const double eps = 1e-10;
typedef long long ll;
typedef double db;
template <class T>
void read(T &x)
{
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-') op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op) x = -x;
}
template <class T>
void write(T x)
{
if(x < 0) putchar('-'), x = -x;
if(x >= 10) write(x / 10);
putchar('0' + x % 10);
}
const int N = 1e5 + 5;
struct node
{
int l,r,nxt;
db w;
}a[N];
int lst[N],len = 0;
int n,m,judge = 0;
void add(int x,int y,db w)
{
a[++len].l = x;
a[len].r = y;
a[len].w = w;
a[len].nxt = lst[x];
lst[x] = len;
}
int vis[N];
db d[N];
void check(int now,db x)
{
vis[now] = 1;
for(int k = lst[now];k;k = a[k].nxt)
{
int y = a[k].r;
if(d[y] > d[now] + a[k].w - x)
{
if(vis[y] || judge)
{
judge = 1;
break;
}
d[y] = d[now] + a[k].w - x;
check(y,x);
}
}
vis[now] = 0;
}
int main()
{
read(n);read(m);
duke(i,1,m)
{
int x,y;
db dis;
read(x);read(y);
scanf("%lf",&dis);
add(x,y,dis);
}
db l = -1e6,r = 1e6;
while(r - l > eps)
{
db mid = (l + r) / 2;
clean(vis);
clean(d); judge = 0;
duke(i,1,n)
{
check(i,mid);
if(judge)
{
break;
}
}
if(judge) r = mid;
else l = mid;
}
printf("%.8lf\n",l);
return 0;
}