刷题记录:牛客NC20684wpy的请求 [图论思维题]
传送门:牛客
题目描述:
“题目名称只是吸引你来做题的啦，其实和题目没什么卵关系：o(*￣▽￣*)o” —— 历史——殿堂
wpy移情别恋啦，他不喜欢spfa了，现在他喜欢使用dij，但是他又发现了一个新的问题，dij无法
跑有负权边的图，于是wpy找到了她的男朋友也就是你来帮忙，为了你晚上的幸福生活，你必须
在1秒内帮她解决这个问题，然后蹿到床上。。。balabala（捂脸）。。。。(*/ω＼*)
简单来说，有一张n个点，m条边的有向图，请你给每条边确定一个新的边权（不同边之间可以不
同），保证对于任意u，v，在新图上的u到v的最短路上的点和原图上最短路上的点相同且顺序不
变。
新的边权要求非负。
输入:
5 10
1 2 -4383
1 3 -9930
2 4 -7331
1 5 -2175
2 3 11962
2 5 16382
4 5 11420
1 4 37978
3 5 13836
3 4 14617
输出:
1 2 0
1 3 0
2 4 0
1 5 0
2 3 17509
2 5 14174
4 5 1881
1 4 49692
3 5 6081
3 4 16401
这道题的思维难度极高,感觉牛客5星名副其实,如果没有看题解的话,我感觉我根本想不出来,这就像做CF上的某些思维题一样绝望.一想到正解做法就会感觉十分的巧妙.这道题值得收藏好吧
主要思路:
- 题目表述十分清楚,显然是需要 S p f a Spfa Spfa,但是此时需要我们改边权,将其改为正的,这该怎么办呢.我们知道 S p f a Spfa Spfa来跑最短路的算法是不断的进行松弛操作,也就是假设当前 d i s [ v ] > d i s [ u ] + e d g e [ u ] [ v ] . w dis[v]>dis[u]+edge[u][v].w dis[v]>dis[u]+edge[u][v].w的时候就松弛一下.那么当我们跑完最终的最短路的时候,我们保证了所有的 u , v u,v u,v都满足 d i s [ u ] + e d g e [ u ] [ v ] . w > = d i s [ v ] dis[u]+edge[u][v].w>=dis[v] dis[u]+edge[u][v].w>=dis[v]
- 那么此时题解的方法就是建立一个超级源点0将其和每一个点链接一条权值为0的边,此时我们可以跑一边Spfa求出所有的dis.然后我们就将每一条边改为 d i s [ u ] − d i s [ v ] + e d g e [ u ] [ v ] . w dis[u]-dis[v]+edge[u][v].w dis[u]−dis[v]+edge[u][v].w,首先这个显然是正的,满足我们的题意,接着我们再来看看他是否满足最短路的条件
我们假设u,v是两个节点,u,v的最短路中途经过了 x 1 , x 2 . . . x n x_1,x_2...x_n x1,x2...xn这些点
因为是最短路,所以
d
i
s
t
[
u
]
[
x
1
]
+
+
d
i
s
t
[
x
1
]
[
x
2
]
+
.
.
.
+
d
i
s
t
[
x
n
−
1
]
[
x
n
]
+
d
i
s
t
[
x
n
]
[
v
]
dist[u][x_1]++dist[x_1][x_2]+...+dist[x_{n-1}][x_{n}]+dist[x_{n}][v]
dist[u][x1]++dist[x1][x2]+...+dist[xn−1][xn]+dist[xn][v]最短
然后我们再来看看我们新图,我们计算一下此时u,v的距离
d i s [ u ] + d i s t [ u ] [ x 1 ] − d i s [ x 1 ] + d i s [ x 1 ] + d i s t [ x 1 ] [ x 2 ] − d i s [ x 2 ] + . . . + d i s [ x n − 1 ] + d i s t [ x n − 1 ] [ x n ] − d i s [ x n ] + + d i s [ x n ] + d i s t [ x n ] [ v ] − d i s [ v ] dis[u]+dist[u][x_1]-dis[x_1]+dis[x_1]+dist[x_1][x_2]-dis[x_2]+...+dis[x_{n-1}]+dist[x_{n-1}][x_{n}]-dis[x_{n}]++dis[x_{n}]+dist[x_{n}][v]-dis[v] dis[u]+dist[u][x1]−dis[x1]+dis[x1]+dist[x1][x2]−dis[x2]+...+dis[xn−1]+dist[xn−1][xn]−dis[xn]++dis[xn]+dist[xn][v]−dis[v]
也就是 d i s [ u ] − d i s [ v ] + d i s t [ u ] [ x 1 ] + + d i s t [ x 1 ] [ x 2 ] + . . . + d i s t [ x n − 1 ] [ x n ] + d i s t [ x n ] [ v ] dis[u]-dis[v]+dist[u][x_1]++dist[x_1][x_2]+...+dist[x_{n-1}][x_{n}]+dist[x_{n}][v] dis[u]−dis[v]+dist[u][x1]++dist[x1][x2]+...+dist[xn−1][xn]+dist[xn][v]
我们会发现无论对于任意两个点来说,我们的dis数组的贡献是一样的(无论中间点是什么),所以此时我们最短路还是由我们原图中的边来决定的.此时就保证了原图中的最短路新图还是最短路这个条件
下面是这道题的代码部分:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
const double eps=1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Node{
int v,w;
};
vector<Node>edge[maxn];
int vis[maxn],dis[maxn];
int n,m;
void Spfa(int S) {
queue<int>q;
for(int i=1;i<=n;i++) dis[i]=int_INF;
q.push(S);
while(!q.empty()) {
int u=q.front();q.pop();
vis[u]=0;
for(int i=0;i<edge[u].size();i++) {
int v=edge[u][i].v;
if(dis[v]>dis[u]+edge[u][i].w) {
dis[v]=dis[u]+edge[u][i].w;
if(!vis[v]) q.push(v);
}
}
}
}
int u[maxn],v[maxn],w[maxn];
int main() {
n=read();m=read();
for(int i=1;i<=m;i++) {
u[i]=read(),v[i]=read(),w[i]=read();
edge[u[i]].push_back({v[i],w[i]});
}
for(int i=1;i<=n;i++) edge[0].push_back({i,0});
Spfa(0);
for(int i=1;i<=m;i++) {
printf("%d %d %d\n",u[i],v[i],dis[u[i]]-dis[v[i]]+w[i]);
}
return 0;
}