[HNOI2009]最小圈 分数规划 spfa判负环

题面

思路难，代码简单。

题目求圈上最小平均值，问题可看为一个0/1规划问题，每个边有\(a[i],b[i]\)两个属性，\(a[i]=w(u,v),b[i]=1\)，问题转化为\(min(\frac{\sum^{k}_{i=1}a[i]}{\sum^{k}_{j=1}b[j]})\)

分数规划考虑二分答案，当前\(mid\)可能为答案当且仅当：

化简即为判定：

每次二分答案时，将图中所有边权\(a[i]​\)视为\(a[i]-mid​\)，此时问题转换为一个\(spfa​\)判负环问题，考虑使用\(dfs​\)优化的\(spfa​\)

AC Code:

#include <cstdio>

#include <cstring>

#define MAXN 3003

#define MAXM 10010

using namespace std;

int head[MAXN],nxt[MAXM],vv[MAXM],tot;

double ww[MAXM];

inline void add_edge(int u, int v, double w){

    vv[++tot]=v;

    ww[tot]=w;

    nxt[tot]=head[u];

    head[u]=tot;

}

double dis[MAXN];

bool vis[MAXN];

bool spfa(int u, double mid){

    vis[u]=1;

    for(register int i=head[u];i;i=nxt[i]){

        int v=vv[i];double w=ww[i]-mid;

        if(dis[v]>dis[u]+w){

            dis[v]=dis[u]+w;

            if(vis[v]) return 1;

            if(spfa(v,mid)) return 1;

        }

    }

    vis[u]=0;

    return 0;

}

inline int read()

{

    int s=0,f=1;

    char ch=getchar();

    while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}

    while (ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}

    return s*f;

}

int n,m;

int main()

{

    n=read(),m=read();

    while(m--){

        int a,b;double w;a=read(),b=read();scanf("%lf", &w);

        add_edge(a,b,w);

    }

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

    while(r-l>1e-10){

        mid=(l+r)/2;

        memset(dis, 0, sizeof(dis));

        memset(vis, 0, sizeof(vis));

        bool isOK=0;

        for(register int i=1;i<=n;++i)

            if(spfa(i,mid)){

                isOK=1;break;

            }

        if(isOK) r=mid;

        else l=mid;

    }

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

    return 0;

}