【HNOI2009】最小圈题解（SPFA判负环+二分答案）

前言：模拟赛考试题，不会做，写了个爆搜滚蛋仍然保龄。

---------------------

题目大意：给定一张有向图，求一个环，使得这个环的长度与这个环的大小（所含结点个数）的比值最小。输出这个比值，保留8位小数。保证数据有解。

---------------------

转化一下题意。要求是使得$C=\frac{\sum\limits_{i=1}^k w[i]}{\sum\limits_{i=1}^k b[i]},b[i]=1$最小。等式变换，得到$\sum\limits_{i=1}^k w[i]-C=0$。我们可以二分这个$C$然后判断有没有负环即可。

貌似看题解是$01$分数规划，我也不太懂。理论上复杂度是$O(nm\log_2 (r-l))$，不过因为算法比较高效也能卡过去。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

const double eps=1e-;

int n,m,vis[maxn];

int head[maxn*],cnt;

struct node

{

    int next,to;

    double dis;

}edge[maxn*];

double dis[maxn];

inline void add(int from,int to,double dis)

{

    edge[++cnt].next=head[from];

    edge[cnt].to=to;

    edge[cnt].dis=dis;

    head[from]=cnt;

}

inline bool spfa(int now,double mid)

{

    vis[now]=;

    for (int i=head[now];i;i=edge[i].next)

    {

        int to=edge[i].to;

        if (dis[to]>dis[now]+edge[i].dis-mid)

        {

            dis[to]=dis[now]+edge[i].dis-mid;

            if (vis[to]||spfa(to,mid)) return ;

        }

    }

    vis[now]=;

    return ;

}

inline bool check(double mid)

{

    for (int i=;i<=n;i++) dis[i]=,vis[i]=;

    for (int i=;i<=n;i++) if (spfa(i,mid)) return ;

    return ;

}

int main()

{

    cin>>n>>m;

    for (int i=;i<=m;i++)

    {

        int x,y;double z;cin>>x>>y>>z;

        add(x,y,z);

    }

    double l=-1e7,r=1e7;

    while(r-l>eps)

    {

        double mid=(l+r)/2.0;

        if (check(mid)) r=mid;

        else l=mid;

    }

    printf("%.8lf",r);

    return ;

}

巴特西

【HNOI2009】最小圈题解（SPFA判负环+二分答案）

最新文章

热门文章

巴特西

【HNOI2009】最小圈 题解（SPFA判负环+二分答案）

最新文章

热门文章

【HNOI2009】最小圈题解（SPFA判负环+二分答案）