跳蚤公路

题意

给定一个有向图，每条边带权，且属于三种类型之一：红色、绿色和白色。跳蚤国王会选定一个整数 $x$，将所有红色边的权值增加 $x$，绿色边的权值减小 $x$。对 $i=1..n$，求使得图中不存在从 $1$ 到 $i$ 包含负环的路径的 $x$ 的取值范围。

解析

考虑在 $x$ 确定的情况下，判断是否存在负环的这一过程。

利用 Bellman Ford 算法，设 $F[i][j]$ 为从 $1$ 出发，至多经过 $i$ 条边，到达 $j$ 的最短路程。如果原图中存在负环，则 $\exists u,F[n][u]<F[n-1][u]$；并且，对于这些满足 $F[n][u]<F[n-1][u]$ 的节点 $u$ 能够到达的节点 $i$，从 $1$ 到 $i$ 的路径都包含负环。

设 $G[i][j][k]$ 为从 $1$ 出发，至多经过 $i$ 条边，走过的绿色边恰好比走过的红色边多 $k$ 条的最短路。则 $F[i][j]=\min\{G[i][j][k]+kx\}$。于是，对于每个 $u$ 所能到达的节点 $i$，我们都要求这个 $i$ 对应的答案 $x$ 满足 $F[n][u]=F[n-1][u]$，即 $\min\{G[n][u][k]+kx\}\ge\min\{G[n-1][u][j]+jx\}$。

发现 $\min a$ 和 $\min b$ 都呈凸包状，解集是连续的。根据这一点性质，没有必要像下面的实现那样复杂了。

实现

#include <bits/stdc++.h>

typedef long long int ll;
typedef long double real;
const int maxn = 1e2 + 9;
const ll inf = 4e18;

void chkmin(ll &a, const ll &b){
    if(b < a) a = b;
}

struct Edge{
    int to, next, dist, tp;
}edge[maxn * maxn];

int head[maxn];

inline void add(int from, int to, int dist, int tp){
    edge[++head[0]] = (Edge){to, head[from], dist, tp};
    head[from] = head[0];
}

int n, m, color_cnt[maxn], tot, cor[maxn];
ll G[maxn][maxn][maxn << 1];
std::vector<std::pair<std::pair<ll, ll>, int> > ans[maxn];
std::vector<int> to;
bool vist[maxn], ok[maxn];

inline void ins(int x){
    tot -= (bool)cor[x];
    ++cor[x];
    tot += (bool)cor[x];
}

inline void del(int x){
    tot -= (bool)cor[x];
    --cor[x];
    tot += (bool)cor[x];
}

ll range_union(const std::vector<std::pair<std::pair<ll, ll>, int> > &s, int cc){
    std::vector<ll> tmp;
    std::vector<std::vector<int> > all;

    for(int i = 0; i < (int)s.size(); ++i)
        tmp.push_back(s[i].first.first), tmp.push_back(s[i].first.second);
    std::sort(tmp.begin(), tmp.end()), tmp.resize(std::unique(tmp.begin(), tmp.end()) - tmp.begin());
    all.resize(tmp.size());

    for(int i = 0; i < (int)s.size(); ++i){
        int x = std::lower_bound(tmp.begin(), tmp.end(), s[i].first.first) - tmp.begin(),
            y = std::lower_bound(tmp.begin(), tmp.end(), s[i].first.second) - tmp.begin();
        all[x].push_back(s[i].second), all[y].push_back(-s[i].second);
    }

    ll res = 0ll;
    for(int i = 0; i < (int)tmp.size() - 1; ++i){
        for(int j = 0; j < (int)all[i].size(); ++j)
            if(all[i][j] > 0)
                ins(all[i][j]);
            else
                del(-all[i][j]);
        if(tot == cc)
            res += tmp[i + 1] - tmp[i];
    }

    std::fill(cor + 1, cor + 1 + n, 0), tot = 0;

    if(res > ll(1e18)) return -1;
    return res;
}

void dfs(int node){
    vist[node] = true, to.push_back(node), ++color_cnt[node];
    for(int i = head[node]; i; i = edge[i].next)
        if(!vist[edge[i].to])
            dfs(edge[i].to);
}

std::pair<ll, ll> operator&(const std::pair<ll, ll> &a, const std::pair<ll, ll> &b){
    return std::make_pair(std::max(a.first, b.first), std::min(a.second, b.second));
}

int main(){
    std::scanf("%d%d", &n, &m);
    for(int i = 1, u, v, w, s; i <= m; ++i){
        std::scanf("%d%d%d%d", &u, &v, &w, &s);
        add(u, v, w, s);
    }

    for(int i = 0; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            for(int k = -n; k <= n; ++k)
                G[i][j][k + n] = inf;
    G[0][1][n] = 0;

    for(int i = 0; i < n; ++i)
        for(int j = 1; j <= n; ++j)
            for(int k = -i; k <= i; ++k)
                if(G[i][j][k + n] != inf)
                    for(int p = head[j]; p; p = edge[p].next){
                        chkmin(G[i + 1][edge[p].to][k + edge[p].tp + n], G[i][j][k + n] + edge[p].dist);
                        chkmin(G[i + 1][j][k + n], G[i][j][k + n]);
                    }

    dfs(1);
    for(int i = 0; i < (int)to.size(); ++i) ok[to[i]] = true, --color_cnt[to[i]];

    for(int i = 1; i <= n; ++i){
        std::fill(vist + 1, vist + 1 + n, false);
        if(!ok[i]) continue;
        to.clear(), dfs(i);
        for(int j = -n; j <= n; ++j){
            if(G[n - 1][i][j + n] == inf) continue;
            std::pair<ll, ll> res(-inf, inf);
            for(int k = -n; k <= n && res.first <= res.second; ++k){
                if(G[n][i][k + n] == inf) continue;
                ll c = j - k, v = G[n][i][k + n] - G[n - 1][i][j + n];
                if(c == 0){
                    if(v < 0) res = std::make_pair(inf, -inf);
                    continue;
                }
                else if(c > 0) res = res & std::make_pair(-inf, std::floor((real)v / (real)c));
                else res = res & std::make_pair(std::ceil((real)v / (real)c), inf);
            }
            if(res.first <= res.second){
                ++res.second;
                for(int k = 0; k < (int)to.size(); ++k)
                    ans[to[k]].push_back(std::make_pair(res, i));
            }
        }
    }

    for(int i = 1; i <= n; ++i)
        if(ok[i])
            std::printf("%lld\n", range_union(ans[i], color_cnt[i]));
        else
            std::puts("-1");

    return 0;
}

来源

UOJ Round #2 B 跳蚤公路

评论