BZOJ 1486: [HNOI2009]最小圈 – [分数规划/负环]


题目传送门(BZOJ)
>原文链接<

题解 :

分数规划题,二分答案。

考虑某答案ans,它可行当且仅当有一环ans \ge (\sum\limits_{i=1}^{cnt}dis[i][i+1])\div cnt 其中cnt是环上点的个数

移项ans\times cnt \ge \sum\limits_{i=1}^{cnt}dis[i][i+1] 其中ans的数量恰好等于dis的数量,都是cnt

那么就变成了\sum\limits_{i=1}^{cnt}(dis[i][i+1]-ans) \le 0

由于ii+1是由某条边直接相连的,所以我们可以把所有边都减掉ans

这样,如果有某个答案符合条件,\sum\limits_{i=1}^{cnt}dis[i][i+1] \le 0 ,就是有一个负环。

如果二分某个答案有负环,那么这个答案就可行,而且可以更小,把r调成mid,否则就太大了,把l调成mid

为了防止精度出问题,我采取迭代T = 60 次的方法,在这道题上表现良好

代码 :

#include 
#include 
#include 
#include 
#define f2 double
#define rev(i, p) for(Edge *i = h[p]; i; i = i->next)
const int N = 3100, M = 11000;
struct Edge {
    int to;
    f2 val;
    Edge *next;
}*h[N],e[M];
int _, n, m;
int ra[M], rb[M];
f2 rv[M];
inline void Add_Edge(int u, int v, f2 w) {
    Edge *tmp = &e[++_];
    tmp->to = v;
    tmp->val = w;
    tmp->next = h[u];
    h[u] = tmp;
}
inline void build(f2 mid) {
    _ = 0; memset(h, 0, sizeof h);
    for(int i = 1; i <= m; i ++ ) {
        Add_Edge(ra[i], rb[i], rv[i]-mid);
    }
}
bool flag, tag[N];
f2 dis[N];
void spfa(int p) {
    tag[p] = 1;
    rev(i, p) if(dis[i->to] > dis[p]+i->val) {
        if(tag[i->to]) {
            flag = 1;
            break;
        }
        dis[i->to] = dis[p]+i->val;
        spfa(i->to);
    }
    tag[p] = 0;
}
inline bool check() {
    memset(dis, 0, sizeof dis); 
    memset(tag, 0, sizeof tag);
    flag = 0;
    for(int i = 1; i <= n; i ++ ) {
        spfa(i);
        if(flag) return 1;
    }
    return 0;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i ++ ) {
        scanf("%d%d%lf", &ra[i], &rb[i], &rv[i]);
    }
    f2 l = -1e9, r = 1e9;
    int T = 60;
    while(T -- ) {
        f2 mid = (l+r)/2;
        build(mid);
        if(check()) r = mid;
        else l = mid;
    }
    printf("%.8f\n", l);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注