裸题，第二个权值是自己点的个数。二分之后用spfa判负环就行了。
题目描述 考虑带权的有向图G=(V,E)G=(V,E)G=(V,E)以及w:E→Rw:E ightarrow Rw:E→R,每条边e=(i,j)(i≠j,i∈V,j∈V)e=(i,j)(i eq j,iin V,jin 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_iin V)c=(c1,c2,⋯,ck)(ci∈V)是GGG中的一个圈当且仅当(ci,ci+1)(1≤i<k)(c_i,c_{i+1})(1le 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/kmu(c)=sumlimits_{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 ightarrow 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 ",l); return 0; }