[HNOI2009]最小圈(分数规划+SPFA判负环)

时间:2021-04-03 05:27:01

题解:求环长比环边个数的最小值,即求min{Σw[i]/|S|},其中i∈S。这题一眼二分,然后可以把边的个数进行转化,假设存在Σw[i]/|S|<=k,则Σw[i]-k|S|<=0,即Σ(w[i]-k)<=0,然后就是表示图中存在负环,可以用spfa跑一下。不过图不保证连通,所以要从每个点分开跑SPFA,还要打标记,访问过的点不能再访问,复杂度O(n^2logw)

#include<bits/stdc++.h>
using namespace std;
const int N=;
int n,m,ecnt,hd[N],v[N],nxt[N],vis[N],used[N],tim[N];
double w[N],d[N];
bool spfa(int S,double k)
{
queue<int>q;q.push(S);
for(int i=;i<=n;i++)vis[i]=,tim[i]=,d[i]=1e18;
d[S]=,tim[S]=;
while(!q.empty())
{
int u=q.front();q.pop();vis[u]=,used[u]=;
for(int i=hd[u];i;i=nxt[i])
if(d[v[i]]>d[u]+w[i]-k)
{
d[v[i]]=d[u]+w[i]-k;
if(!vis[v[i]])q.push(v[i]),vis[v[i]]=,tim[v[i]]++;
if(tim[v[i]]>)return ;
}
}
return ;
}
bool check(double val)
{
memset(used,,sizeof used);
for(int i=;i<=n;i++)if(!used[i]&&spfa(i,val))return ;
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x,y;i<=m;i++)
{
double z;scanf("%d%d%lf",&x,&y,&z);
v[++ecnt]=y,nxt[ecnt]=hd[x],w[ecnt]=z,hd[x]=ecnt;
}
double l=-1e7-,r=1e7+;
while(r-l>1e-)
{
double mid=(l+r)/;
if(check(mid))r=mid;else l=mid;
}
printf("%.8lf",l);
}