首页 > 代码库 > bzoj1690

bzoj1690

2024-11-19 14:21:02   203人阅读

二分+分数规划+dfs判环

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

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

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

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

技术分享 
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
struct ed {
    int to;
    double w;
    ed(int to = 0, double w = 0) : to(to), w(w) {}
};
struct Edge {
    int u, v;
    double t;
    Edge(int u = 0, int v = 0, double t = 0) : u(u), v(v), t(t) {}
} edge[N * 5];
int n, m;
int cnt[N], q[N * 110], vis[N];
double d[N], f[N];
vector<ed> G[N];
bool dfs(int u)
{
    vis[u] = 1;
    for(int i = 0; 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] = 0;
    return false;
}
bool check(double mid)
{
    for(int i = 1; i <= n; ++i) 
    {
        d[i] = -1e9;
        vis[i] = 0;
        G[i].clear();
    }
    for(int i = 1; i <= m; ++i) G[edge[i].u].push_back(ed(edge[i].v, f[edge[i].u] - mid * edge[i].t));
    for(int i = 1; i <= n; ++i) if(dfs(i)) return true;
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%lf", &f[i]);
    for(int i = 1; i <= m; ++i) scanf("%d%d%lf", &edge[i].u, &edge[i].v, &edge[i].t);
    double l = 0, r = 1010, ans;
    while(r - l > 1e-4)
    {
        double mid = (l + r) / 2.0;
        if(check(mid)) l = ans = mid;
        else r = mid;
    }
    printf("%.2f\n", ans);
    return 0;
}
View Code

 

bzoj1690


联系
我们