二分答案是显然的，我们需要dfs版spfa判一下负环。
看起来是n^2其实很快。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxv 3050 #define maxe 10050 #define eps 1e-9 #define inf 0x7f7f7f7f7f7f7f7fLL using namespace std; struct edge { int v,nxt; double c,w; }e[maxe]; int n,m,x,y,g[maxv],nume=1,flag; double z,dis[maxv],l,r,ans; bool vis[maxv]; void addedge(int u,int v,double w) { e[++nume].v=v;e[nume].c=w; e[nume].nxt=g[u];g[u]=nume; } void rebuild(double x) { for (int i=2;i<=nume;i++) e[i].w=e[i].c-x; } void dfs(int x) { vis[x]=true; for (int i=g[x];i;i=e[i].nxt) { int v=e[i].v; if (dis[v]>dis[x]+e[i].w) { if (!vis[v]) {dis[v]=dis[x]+e[i].w;dfs(v);} else {flag=1;break;} } } vis[x]=false; } bool check(double x) { rebuild(x);flag=0; for (int i=1;i<=n;i++) {vis[i]=false;dis[i]=0;} for (int i=1;i<=n;i++) { dfs(i); if (flag) return true; } return false; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { scanf("%d%d%lf",&x,&y,&z); addedge(x,y,z); } ans=-1;l=-inf;r=inf; while (r-l>=eps) { double mid=(l+r)/2; if (check(mid)) r=mid; else {ans=mid;l=mid;} } printf("%.8lf ",ans); return 0; }