名題期末提分計劃答案，bzoj千題計劃227：bzoj1486: [HNOI2009]最小圈

2023-10-09 阅读 23 评论 0

摘要：http://www.lydsy.com/JudgeOnline/problem.php?id=1486 ? 二分答案 dfs版spfa判負環名題期末提分計劃答案？? #include<queue> #include<cstdio> #include<cstring> #include<iostream>#define N 3001 #define M 10001using namespace std;int

http://www.lydsy.com/JudgeOnline/problem.php?id=1486

二分答案

dfs版spfa判負環

名題期末提分計劃答案？?

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>#define N 3001
#define M 10001using namespace std;int n;int tot,front[N],nxt[M],to[M];
double val[M];double Val[M];double dis[N];
bool vis[N];bool tag;queue<int>q;int s;void read(int &x)
{x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }
}void add(int u,int v,double w)
{to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;
}    void spfa(int u)
{//if(tag) return;int t;for(int i=front[u];i;i=nxt[i]){t=to[i];if(dis[u]+Val[i]<dis[t]){dis[t]=dis[u]+Val[i];if(!vis[t]){vis[t]=true;spfa(t);vis[t]=false;if(tag) return;}else {tag=true;return;}}}
}bool check(double mid)
{for(int i=1;i<=tot;++i) Val[i]=val[i]-mid;tag=false;for(int i=1;i<=n;++i){    for(int j=1;j<=n;++j) dis[j]=0;vis[i]=true;spfa(i);vis[i]=false;if(tag) return true;}return false;
}int main()
{int m;read(n); read(m);int u,v; double w;while(m--){read(u); read(v); scanf("%lf",&w);add(u,v,w);}double l=-1e6,r=1e6,mid,ans;int T=55;while(T--){mid=(l+r)/2;if(!check(mid)) ans=l,l=mid;else r=mid;}printf("%.8lf",ans);
}