[BZOJ1486][HNOI2009]最小圈（01分数规划+深搜spfa）

题目描述

传送门

题解

01分数规划 如果存在负权环的话说明有更优的答案 写深搜spfa就不会tle了

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 20005 const double eps=1e-9; const double inf=1e9; int n,m; int tot,point[N],nxt[N],v[N];double c[N]; double dis[N],ans; bool vis[N],flag; void add(int x,int y,double z) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; c[tot]=z; } void spfa(int x,double mid) { vis[x]=1; for (int i=point[x];i;i=nxt[i]) if (dis[v[i]]>dis[x]+c[i]-mid) { dis[v[i]]=dis[x]+c[i]-mid; if (vis[v[i]]) { flag=1; return; } spfa(v[i],mid); if (flag) return; } vis[x]=0; } bool check(double mid) { memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); for (int i=1;i<=n;++i) { flag=0; spfa(i,mid); if (flag) return 1; } return 0; } double find() { double l=-inf,r=inf,mid,ans=inf; while (r-l>eps) { mid=(l+r)/2.0; if (check(mid)) ans=r=mid; else l=mid; } return ans; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=m;++i) { int x,y;double z;scanf("%d%d%lf",&x,&y,&z); add(x,y,z); } ans=find(); printf("%.8lf\n",ans); }