【BZOJ1486】[HNOI2009]最小圈
Description
Input
Output
Sample Input
4 5
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
1 2 5
2 3 5
3 1 5
2 4 3
4 1 3
Sample Output
3.66666667
题解：题意给的实在不能太明显了，直接上分数规划。二分答案mid，将边权改为（原边权-mid），然后spfa判断是否有负环，若有则调整上界，否则调整下界。
然而码完一发交上去TLE，看了题解发现这题居然要用DFS版的SPFA！有谁能一上来就想到用DFS的我也是醉了~
#include <cstdio>
#include <cstring>
#include <iostream>
#define eps 1e-9
using namespace std;
int n,m,cnt,ok;
int pa[10010],pb[10010];
int head[3010],to[10010],next[10010],vis[3010];
double val[10010],dis[3010],pc[10010];
void add(int a,int b,double c)
{
to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x)
{
vis[x]=1;
for(int i=head[x];i!=-1&&!ok;i=next[i])
{
if(dis[to[i]]>dis[x]+val[i])
{
dis[to[i]]=dis[x]+val[i];
if(vis[to[i]])
{
ok=1; return ;
}
dfs(to[i]);
}
}
vis[x]=0;
}
int solve(double sta)
{
int i,u;
memset(head,-1,sizeof(head)),cnt=0;
memset(vis,0,sizeof(vis));
for(i=1;i<=m;i++) add(pa[i],pb[i],pc[i]-sta);
for(i=1;i<=n;i++) dis[i]=0;
for(i=1,ok=0;i<=n;i++)
{
dfs(i);
if(ok) return 1;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int i,j,a,b;
double l=10000000,r=0,mid;
for(i=1;i<=m;i++) scanf("%d%d%lf",&pa[i],&pb[i],&pc[i]),l=min(l,pc[i]),r=max(r,pc[i]);
while(r-l>eps)
{
mid=(l+r)*0.5;
if(solve(mid)) r=mid;
else l=mid;
}
printf("%.8f",r);
return 0;
}