首页 > 其他 > 详细

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

时间:2019-04-21 22:49:07      阅读:120      评论:0      收藏:0      [点我收藏+]

题解:求环长比环边个数的最小值,即求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=11100;
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=1;i<=n;i++)vis[i]=0,tim[i]=0,d[i]=1e18;
    d[S]=0,tim[S]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();vis[u]=0,used[u]=1;
        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]]=1,tim[v[i]]++;
            if(tim[v[i]]>50)return 1;
        }
    }
    return 0;
}
bool check(double val)
{
    memset(used,0,sizeof used);
    for(int i=1;i<=n;i++)if(!used[i]&&spfa(i,val))return 1;
    return 0;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1,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-100,r=1e7+100;
    while(r-l>1e-9)
    {
        double mid=(l+r)/2;
        if(check(mid))r=mid;else l=mid;
    }
    printf("%.8lf",l);
}
View Code

 

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

原文:https://www.cnblogs.com/hfctf0210/p/10747360.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!