BZOJ1486 HNOI2009 最小圈
Description
应该算是01分数规划的裸板题了吧。。但是第一次写还是遇到了一些困难，vis数组不清零之类的
假设一个答案成立，那么一定可以找到一个环使得其边权和大于等于边数∗ans。
可以发现答案是具有二分性的，二分出一个临时答案ans′，并且用ans′对每条边进行约束，再用深搜SPFA判断一下负环，如果有负环说明当前解可行，继续二分就好了。
注意题目要求保留到小数点后八位，多开一点二分次数防止精度不够啊
/**************************************************************
Problem: 1486
User: yangkai
Language: C++
Result: Accepted
Time:2292 ms
Memory:1648 kb
****************************************************************/
#include<bits/stdc++.h>
using namespace std;
int read(){
int ans=0,w=1;char c=getchar();
while(c!='-'&&!isdigit(c))c=getchar();
if(c=='-')w=-1,c=getchar();
while(isdigit(c))ans=ans*10+c-'0',c=getchar();
return ans*w;
}
#define N 3010
#define M 10010
#define INFF 10000000
int n,m,tot,head[N];
struct Edge{int v,next;double w;}E[M];
void add(int u,int v,double w){
E[++tot]=(Edge){v,head[u],w};head[u]=tot;
}
int u[M],v[M],vis[N];
double w[M],dis[N];
void build(double val){
for(int i=1;i<=n;i++)head[i]=0;tot=0;
for(int i=1;i<=m;i++)add(u[i],v[i],w[i]-val);
}
bool flag=0;
void SPFA(int x){
vis[x]=1;
for(int i=head[x];i;i=E[i].next){
int y=E[i].v;
if(dis[x]+E[i].w<dis[y]){
if(vis[y]){flag=1;break;}
else{
dis[y]=dis[x]+E[i].w;
SPFA(y);
}
}
}
vis[x]=0;
}
int main(){
n=read();m=read();
for(int i=1;i<=m;i++){
u[i]=read(),v[i]=read();
scanf("%lf",&w[i]);
}
double l=-INFF,r=INFF;
for(int p=1;p<=60;p++){
double mid=(l+r)/2;
build(mid);
flag=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
memset(dis,0,sizeof(dis));
SPFA(i);
if(flag)break;
}
if(flag)r=mid;
else l=mid;
}
printf("%.8lf",l);
return 0;
}