题解 P3199 【[HNOI2009]最小圈】

· · 题解

最小圈

Preface 前言

双（三）倍经验！

所以，你们可能会在 UVA11090 Going in Cycle!! 这篇题解中又看到我qwq

Problem model 问题模型

这三道题都是给定一张有向图，首先判断是否有环

如果有环就求出最大环或最小环的平均值

解决这种题，我们通常都是使用 二分答案 & SPFA 判环求最短（长）路

Train of thought 思路点拨

因为在找最大（小）环的时候我们一般会想到：

遍历整个图，找到每一个环，然后算出它们的平均值，最后比较出最大（小）值

但是题目可能是多组数据，还不说图的大小，所以这种思路大概率会 T 飞的

——不能找环，那我们就直接找答案啊！（这里要转换一下思想）

因为找答案 = 枚举答案，而枚举答案一般使用较高效的二分答案！

我们能将求答案ans的式子表示如下：

ans=(len_1+len_2+len_3+···+len_k)/K

数学转换一下：

ans*K=len_1+len_2+len_3+···+len_k

移项一下：

(len_1+len_2+len_3+···+len_k)-ans*K=0

最后我们可得：

(len_1-ans)+(len_2-ans)+(len_3-ans)+···+(len_k-ans)≥0

（因为最开始的式子是整除，会有精度问题，所以是 ≥ ）

dis[v]>dis[now]+e[i].val-mid 或 dis[v]<dis[now]+e[i].val-mid

则 dis[v]=dis[now]+e[i].val-mid

其中 mid 是我们当前枚举的答案（第一句是最小环，第二句是最大环）

每次枚举了 ans，就跑 SPFA ，如果存在环则说明当前枚举的 ans 是合法的，反之不合法

Code 代码

注：这三道题我都写的 dfs 版的 SPFA

#include <bits/stdc++.h>
using namespace std;
int n,m,u,v,tot;
double w,dis[520010];
int vis[520010],head[520010];

struct node {
    int to,net;
    double val;
} e[520010];

inline void add(int u,int v,double w) {
    e[++tot].to=v;
    e[tot].val=w;
    e[tot].net=head[u];
    head[u]=tot;
}

inline bool dfs(int now,double x) {
    vis[now]=1;
    for(register int i=head[now];i;i=e[i].net) {
        int v=e[i].to;
        if(dis[v]>dis[now]+e[i].val-x) {
            dis[v]=dis[now]+e[i].val-x;
            if(vis[v]==1||dfs(v,x)==true) return true;
        }
    }
    vis[now]=0;
    return false;
}

inline bool check(double x) {
    for(register int i=1;i<=n;i++) {
        vis[i]=0;
        dis[i]=20050206;
    }
    for(register int i=1;i<=n;i++) {
        if(dfs(i,x)==true) return true;
    }
    return false;
}

int main() {
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=m;i++) {
        scanf("%d%d%lf",&u,&v,&w);
        add(u,v,w);
    }
    double l=-10000000,r=10000000;
    while(r-l>1e-10) {
        double mid=(l+r)/2;
        if(check(mid)==true) r=mid;
        else l=mid;
    }
    printf("%.8lf",l);
    return 0;
}

Epilogue 尾声

最后，如果这篇题解有任何问题或不懂的地方，欢迎留言区评论

我一定会及时回复、改正，谢谢各位dalao呀！orz