bzoj1690

二分+分数规划+dfs判环

跟1486很像，但是我忘记怎么判环了，

我们可以写一个dfs，如果当前节点的距离小于更新的距离，而且这个点已经在当前访问过了，那么就是有环了，如果没有访问过就继续dfs，每个点枚举dfs就行了。

如果这个点距离大于更新距离，那么没必要访问，因为刚才都没有判出来正环，现在这个距离更小，走原先的路更不可能出现正环了

其实想了想，主要是可能有多个连通块，因为如果一个连通块有环，那么在连通块的任何一个点都能查到环，所以主要是不同的连通块导致的，dfs判环只要一次就行了，不像spfa要n次才行

#include<bits/stdc++.h>

using namespace std;

const int N = ;

struct ed {

    int to;

    double w;

    ed(int to = , double w = ) : to(to), w(w) {}

};

struct Edge {

    int u, v;

    double t;

    Edge(int u = , int v = , double t = ) : u(u), v(v), t(t) {}

} edge[N * ];

int n, m;

int cnt[N], q[N * ], vis[N];

double d[N], f[N];

vector<ed> G[N];

bool dfs(int u)

{

    vis[u] = ;

    for(int i = ; i < G[u].size(); ++i)

    {

        ed e = G[u][i];

        if(d[e.to] < d[u] + e.w)

        {

            if(vis[e.to]) return true;

            d[e.to] = d[u] + e.w;

            if(dfs(e.to)) return true;

        }

    }

    vis[u] = ;

    return false;

}

bool check(double mid)

{

    for(int i = ; i <= n; ++i)

    {

        d[i] = -1e9;

        vis[i] = ;

        G[i].clear();

    }

    for(int i = ; i <= m; ++i) G[edge[i].u].push_back(ed(edge[i].v, f[edge[i].u] - mid * edge[i].t));

    for(int i = ; i <= n; ++i) if(dfs(i)) return true;

    return false;

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = ; i <= n; ++i) scanf("%lf", &f[i]);

    for(int i = ; i <= m; ++i) scanf("%d%d%lf", &edge[i].u, &edge[i].v, &edge[i].t);

    double l = , r = , ans;

    while(r - l > 1e-)

    {

        double mid = (l + r) / 2.0;

        if(check(mid)) l = ans = mid;

        else r = mid;

    }

    printf("%.2f\n", ans);

    return ;

}

巴特西

bzoj1690

最新文章

热门文章