Tag:Fractional programming
Article From:https://www.cnblogs.com/zhoushuyu/p/9060853.html

[BZOJ1486][HNOI2009] minimum loop”

bzoj
luogu

meaning”

You have a directed graph that guarantees connectivity and guarantees that there is at least one ring.
You need to find a ring that minimizes the average weight of the ring.
The average value of a ring is defined as the total weight of a ring divided by the ring length.

sol

Fractional planning. It can be seen as every side\(b_i=1\)
Two points one\(mid\),order\(d_i=w_i-mid\),Then determine whether there is a negative loop in the graph.
The simplest of negative rings\(O(n^2)\)The algorithm can be used.

code

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 10005;
struct edge{int to,nxt;double w;}a[N];
int n,m,head[N],cnt,vis[N];
double dis[N];
void link(int u,int v,double w){
    a[++cnt]=(edge){v,head[u],w};head[u]=cnt;
}
bool cir(int u,double k){
    vis[u]=1;
    for (int e=head[u];e;e=a[e].nxt)
        if (dis[a[e].to]>dis[u]+a[e].w-k){
            dis[a[e].to]=dis[u]+a[e].w-k;
            if (vis[a[e].to]||cir(a[e].to,k)) return true;
        }
    vis[u]=0;return false;
}
bool check(double k){
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    for (int i=1;i<=n;++i) if (cir(i,k)) return true;
    return false;
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i){
        int u,v;double w;
        scanf("%d %d %lf",&u,&v,&w);
        link(u,v,w);
    }
    double l=-2e7,r=2e7;
    while (r-l>1e-9){
        double mid=(l+r)/2;
        if (check(mid)) r=mid;
        else l=mid;
    }
    printf("%.8lf\n",l);
    return 0;
}
Link of this Article: [BZOJ1486][HNOI2009] minimum loop

Leave a Reply

Your email address will not be published. Required fields are marked *