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;
}
0 条评论