1486: [HNOI2009]最小圈

2019-11-06 07:23:52

字体：大中小

来源：转载

供稿：网友

题目链接

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

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

#include <iostream>#include <cstring>#include <cstdio>using namespace std;#define INF 0x3f3f3f3f#define eps 1e-9const 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;}

上一篇：PAT 1120

下一篇：SSH学习之Struts2获取表单数据