[HNOI2009]最小圈

传送门

题意:在带权有向图中,求图中所有环的平均值的最小值(环的平均值即构成环的所有边的边权的平均值).

分析:理解题意,我们要求的实际上就是\(\frac{\sum_{i=1}^k{c_i}}{k}\)

令\(x=\frac{\sum_{i=1}^k{c_i}}{k}\)

整理得\(\sum_{i=1}^k{c_i}-k*x=0\)

继续得\(\sum_{i=1}^k(c_i-x)=0\)

令\(f(x)=\sum_{i=1}^k(c_i-x)\)

f(x)随x增大而减小,即f(x)是一个递减函数,既然具有单调性,就要想到二分答案.

我们直接二分要求的答案x,check时把每条边的边权看作\(c_i-x\),如果此次二分的值合法,即\(\frac{\sum_{i=1}^k{c_i}}{k}<x\),根据上面的推导得\(\sum_{i=1}^k(c_i-x)<0\),即图中存在一个负环.

所以本题就转换为了二分x,把每条边权看作\(c_i-x\),然后判断图中是否存在负环.

我写的是dfs+spfa判负环(如果不会判负环,请看广告).

注意本题是实数域上的二分答案.

int n,m,visit[3005];
int tot,head[3005],nxt[10005],to[10005];
double eps=1e-10;
//要求保留8位小数,二分精度可以设置为1e-(8+2)
double w[10005],dis[3005];
void add(int a,int b,double c){
    nxt[++tot]=head[a];
    head[a]=tot;
    to[tot]=b;
    w[tot]=c;
}
bool dfs_spfa(int x,double mid){
    visit[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
//记得边权看作w[i]-mid 
        if(dis[y]>dis[x]+w[i]-mid){
            dis[y]=dis[x]+w[i]-mid;
            if(visit[y]||dfs_spfa(y,mid))
                return 1;
        }
    }
    visit[x]=0;
    return 0;
}
bool check(double mid){
    memset(visit,0,sizeof(visit));
    for(int i=1;i<=n;i++)dis[i]=0;
//这里为什么dis数组全部初始化为零我也不懂
//反正我试了赋值为无穷大是错的
//(我不会说出来我无脑试了好几个初值)
    for(int i=1;i<=n;i++)
        if(dfs_spfa(i,mid))return 1;
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b;double c;
        scanf("%d%d%lf",&a,&b,&c);
        add(a,b,c);
    }
    double l=-1e9,r=1e9,mid;
//注意一下二分边界,因为环的最小平均值可能为负数
    while(l+eps<r){//实数二分答案模板
        mid=(l+r)/2.0;
        if(check(mid))r=mid;
        else l=mid;
    }
    printf("%.8lf\n",r);
    return 0;
}

[HNOI2009]最小圈

原文：https://www.cnblogs.com/PPXppx/p/10366966.html