首页 > 代码库 > BZOJ 1486 HNOI2009 最小圈 二分答案+DFS
BZOJ 1486 HNOI2009 最小圈 二分答案+DFS
题目大意:裸的最优比例环
直接二分答案+SPFA 这样会T 因为数据卡SPFA
SPFA在负环非常小的时候会退化成Bellman-Ford 时间复杂度是O(nm) (好像是O(n*m^2)?我忘了)的
换一种方法 枚举每个点 从每个点开始DFS 只沿着能将指向的点dis减小的边搜索 搜到栈中的点就返回true
期望复杂度O(n^2) 最坏复杂度O(2^n) 这种东西能过我也是醉了- -
#include <cstdio> #include <cstring> #include <iomanip> #include <iostream> #include <algorithm> #define M 3030 #define EPS 1e-9 #define INF 1e7 using namespace std; struct abcd{ int to,next; double f; }table[10100]; int head[M],tot; int n,m,T; double a[10100],dis[M]; void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } void DFS(int x) { static int v[M]; int i; if(v[x]==T) throw(true); v[x]=T; for(i=head[x];i;i=table[i].next) if(dis[x]+table[i].f<dis[table[i].to]) { dis[table[i].to]=dis[x]+table[i].f; DFS(table[i].to); } v[x]=0; } bool Judge(double x) { int i; for(i=1;i<=m;i++) table[i].f=a[i]-x; for(i=1;i<=n;i++) { try{ ++T; memset(dis,0,sizeof dis); DFS(i); } catch(bool) { return true; } } return false; } double Bisection() { int i; double l=INF,r=-INF; for(i=1;i<=m;i++) l=min(l,a[i]),r=max(r,a[i]); while(r-l>EPS) { double mid=(l+r)/2; if( Judge(mid) ) r=mid; else l=mid; } return (l+r)/2; } int main() { int i,x,y; cin>>n>>m; for(i=1;i<=m;i++) scanf("%d%d%lf",&x,&y,&a[i]),Add(x,y); cout<<fixed<<setprecision(8)<<Bisection()<<endl; return 0; }
BZOJ 1486 HNOI2009 最小圈 二分答案+DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。