1486: [HNOI2009]最小圈

题目链接

题目大意：求平均权最小的环

题解：二分+dfs式spfa判负环

#include <iostream> #include <cstring> #include <cstdio> using namespace std; #define INF 0x3f3f3f3f #define eps 1e-9 const int M=3005; int m,n,t; int head[M]; double z[M*5],d[M]; bool flag,vis[M]; struct edge{int to,nex;double val;}e[M*5]; inline void add(int u,int v){e[t].to=v;e[t].nex=head[u];head[u]=t++;} void dfs(int x) { if(vis[x]) { throw(true); } vis[x]=1; for(int i=head[x];i!=-1;i=e[i].nex) { int v=e[i].to; if(d[v]>d[x]+e[i].val) d[v]=d[x]+e[i].val,dfs(v); } vis[x]=0; } inline bool judge(double x) { for(int i=0;i<t;i++) e[i].val=z[i]-x; for(int i=1;i<=n;i++) d[i]=0,vis[i]=0;flag=0; for(int i=1;i<=n;i++) { try {dfs(i);}//奇怪的东西 catch(bool){return true;} } return false; } void work() { double l,r,mid,ans; l=-INF,r=INF; while(r-l>=eps) { mid=(l+r)/2.0; if(judge(mid)) ans=mid,r=mid; else l=mid; } PRintf("%.8lf\n",ans); } void init() { int x,y; t=0,memset(head,-1,sizeof(head)); cin>>n>>m; for(int i=1;i<=m;i++){ scanf("%d%d%lf",&x,&y,&z[i-1]);//存边权数组编号从0开始…… add(x,y); } } int main() { init(); work(); return 0; }