Sample Input 4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3 Sample Output 3.66666667
解法：01分数规划+SPFA判环
///BZOJ 1486 #include <bits/stdc++.h> using namespace std; const int maxn = 3005; const int maxm = 30005; int n, m, edgecnt, head[maxn]; double dis[maxn]; bool vis[maxn]; struct edge{ int v, nxt; double w; edge(){} edge(int v, int nxt, double w):v(v),nxt(nxt),w(w){} }E[maxm]; int u[maxm], v[maxm]; double w[maxm]; void init(){ memset(head, -1, sizeof(head)); edgecnt=0; } void add(int u, int v, double w){ E[edgecnt].v = v, E[edgecnt].nxt = head[u], E[edgecnt].w = w, head[u] = edgecnt++; } void build(double mid){ init(); for(int i=1; i<=m; i++) add(u[i],v[i],w[i]-mid); } int flag; void spfa(int x){ vis[x]=1; for(int i=head[x];i+1;i=E[i].nxt){ int v=E[i].v; if(dis[x]+E[i].w<dis[v]){ if(vis[v]){ flag=1; } else{ dis[v]=dis[x]+E[i].w; spfa(v); } } } vis[x]=0; } bool check(double mid){ build(mid); memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); flag=0; for(int i=1; i<=n; i++){ spfa(i); if(flag) return 1; } return 0; } int main() { scanf("%d%d", &n,&m); for(int i=1; i<=m; i++){ scanf("%d%d%lf",&u[i],&v[i],&w[i]); } double l = -10000000, r = 10000000; for(int i=0; i<100; i++){ double mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } printf("%.8f\n", l); return 0; }