CF1483D. Useful Edges

题目大意

给你一个 n 个顶点的带权无向图和 q 个三元组 (u,v,l) 。u 和 v 都是顶点，l 是一个正整数。

一条边 e 被称为有用，当且仅当至少存在一个三元组 (u,v,l) 和满足以下条件的一条路径：

• $u$ 和 $v$ 是这条路径的端点
• $e$ 是这条路径的一条边
• 这条路径的所有边的权值和不超过 l

请计算这张图张有多少条有用的路径

Solution

记题目所给的 m 条边为 (u,v,w)

记作原题给的 q 个三元组为 (s,t,l)。

可以考虑枚举 m 条边和 q 个三元组，一一匹配，复杂度 O(n^4)

由于必须要走边 e ，当 e 满足这个式子，e 为 useful edge
dis[s][u]+w_{u,v}+dis[v][t]\leq l_{s,t}
（要想到 dis 可以用 Floyd 算出，因为 s\to u 和 v\to s 中间走了哪里并不需要关心，只需要求最短距离）

然后考虑优化，枚举边肯定是必要的，所以看能不能优化对三元组的枚举。

将 dis[s][u] 移到右边，得到
w_{u,v}+dis[v][t]\leq l_{s,t}-dis[s][u]
可以发现等式左边与 s 无关

由于是 \leq 符号，所以我们希望右边的式子能够最大。对每一个 (t,u) 来说，我们遍历所有的 s，取

l_{s,t}-dis[s][u] 最大的那一个，记作 pre[t][u] 。

也就是说有
pre[t][u]=max_{s=1}^{n}(l_{s,t}-dis[s][u])
预处理的过程为 O(n^3) （枚举三元组和 u）

然后就对每条边枚举一个 t ，看是否能满足
w_{u,v}+dis[v][t]\leq pre[t][u]
复杂度 O(n^3)

#include<bits/stdc++.h>
#define ll long long
using namespace std; 
const int N = 666;
ll dis[N][N];
int n,m,q;
pair<pair<int,int>,ll> p[N*N];
pair<pair<int,int>,ll> r[N*N];
ll pre[N][N];
void floyd(){
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k){
                if(dis[j][i]+dis[i][k]<dis[j][k])
                    dis[j][k] = dis[j][i] + dis[i][k];
            }
}
int main(){
    scanf("%d%d",&n,&m);
    memset(dis,0x3f,sizeof(dis));
    for(int i=1;i<=n;++i)
        dis[i][i] = 0;
    for(int i=1;i<=m;++i){
        int u,v;ll w;
        scanf("%d%d%lld",&u,&v,&w);
        dis[u][v]=w;
        dis[v][u]=w;
        p[i]=make_pair(make_pair(u,v),w);
    }
    floyd();
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        int u,v;ll w;
        scanf("%d%d%lld",&u,&v,&w);
        r[i]=make_pair(make_pair(u,v),w);
    }
    int ans = 0;
    for(int i=1;i<=q;++i){
        int s = r[i].first.first;
        int t = r[i].first.second;
        ll l = r[i].second;
        for(int u=1;u<=n;++u){
            pre[t][u]=std::max(pre[t][u],l-dis[s][u]);
        }
    }
    for(int i=1;i<=m;++i){
        int u = p[i].first.first;
        int v = p[i].first.second;
        ll w = p[i].second;
        for(int t=1;t<=n;++t)
            if(w+dis[v][t]<=pre[t][u]||w+dis[u][t]<=pre[t][v]){
                ans++;
                break; 
            }
    }
    printf("%d",ans);
    return 0;
}