标签：ace   amp   mes   add   变换   pre   double   space   cst   

01规划

设答案为 \(ans\)。

二分答案，设当前二分值为 \(mid\)。

设一个环 \(S\) 的边权为 \(t_1, t_2, t_3...\)，点权为 \(f_1, f_2, f_3...\)

• 若 \(mid ，即存在一个环\(S\)使得 \(mid ，变换一下：\(\sum(mid * t_i - f_i)

• 否则，则 \(mid > ans\)

每次 \(check\) 的时候，一条 \(u\) 指向 \(v\)，边权为 \(w\) 的边权变为：

\(w * mid - f_u\)。我们只需检查这个图是否存在负环即可。

时间复杂度

最坏情况存在长度为 \(L\) 的环， \(\sum t_i = L, \sum f_i = 1000L\)。故答案最大可能是 \(1000\)。

\(Log_21000 \approx 10\)

\(O(10*LP)\)。判负环的时间一般情况下低于 \(O(LP)\)。

#include 
#include 
using namespace std;
const int N = 1005, M = 5005;
int n, q[N * M], m, f[N], cnt[N];
int head[N], numE = 0;
double dis[N];
bool vis[N];
struct E{
    int next, v, w;
}e[M];
void add(int u, int v, int w) {
    e[++numE] = (E) { head[u], v, w };
    head[u] = numE;
}
bool inline check(double mid) {
    int hh = 0, tt = -1;
    for (int i = 1; i = n) return true;
                if(!vis[v]) q[++tt] = v;
            }
        }
    }
    return false;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i  eps) {
        double mid = (l + r) / 2;
        if(check(mid)) l = mid;
        else r = mid;
    }
    printf("%.2lf\n", r);
    return 0;
}

AcWing 361. 观光奶牛

标签：ace   amp   mes   add   变换   pre   double   space   cst   

原文地址：https://www.cnblogs.com/dmoransky/p/11919144.html