膜法森林 2333……
显然是一道 $LCT$ 动态加边的题目。
然而并不需要这么高深的数据结构来动态加边 (实际上是不会)，我们只需要 $Spfa$ 动态加边即可切掉此题。
怎么 $Spfa$? 又是个怎么的动态加边法呢？
在下面我先给出代码，然后再来一步一步剖析 (跟 $Spfa$ 板子差不多)。
Code:
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#define ll long long
#define RI register int
const int N=5e4+2,M=1e5+2;
const int inf=1e9+9;
template <typename _Tp> inline void IN(_Tp&x){
bool flag=0;char ch;x=0;
while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
if(flag)x=-x;
}
bool vis[N];
std::queue<int> q;
int head[N],dis[N],tot,cnt,ans,n,m;
struct Edge_Spfa{int nxt,to,v1,v2;}G[M];
struct Edge_Main{
int x,y,v1,v2;
bool operator < (Edge_Main a)const{
return v1<a.v1;
}
}L[M];
inline void make_line(int x,int y,int v1,int v2){
G[++tot].nxt=head[x],head[x]=tot,G[tot].to=y,G[tot].v1=v1,G[tot].v2=v2;
G[++tot].nxt=head[y],head[y]=tot,G[tot].to=x,G[tot].v1=v1,G[tot].v2=v2;
}
#define A printf("A")
#define C printf("\n")
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
inline void spfa(int star_1,int star_2){
vis[star_1]=true,vis[star_2]=true;
q.push(star_1),q.push(star_2);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i;i=G[i].nxt){
int to=G[i].to;
if(max(dis[u],G[i].v2)<dis[to]){
dis[to]=max(dis[u],G[i].v2);
if(!vis[to])q.push(to),vis[to]=true;
}
}vis[u]=false;
}return;
}
int main(){
IN(n),IN(m);
memset(dis,127,sizeof(dis));
dis[1]=0,q.push(1),ans=inf;
for(int i=1;i<=m;++i)
IN(L[i].x),IN(L[i].y),IN(L[i].v1),IN(L[i].v2);
std::sort(L+1,L+1+m);
for(int i=1;i<=m;++i){
make_line(L[i].x,L[i].y,L[i].v1,L[i].v2);
spfa(L[i].x,L[i].y);
ans=min(ans,dis[n]+L[i].v1);
}printf("%d\n",ans==inf?-1:ans);
return 0;
}
动态加边，顾名思义，就是按最优顺序依次将边插入，对于每次插完边的图做一次答案统计 ($Spfa$)，然后每次在 $main$ 函数里统计答案，最后输出即可。
我们固定 $v1$ ，用 $v2$ 跑 $Spfa$，边的插入顺序是按照 $v1$ 的大小来的，小的先插。
之所以上面要用到 $sort$，是因为我们要达到” 按最优顺序依次将边插入”。
$Spfa$ 的板子就不解释了，不懂的同学左转搜素 $Spfa$ ，先刷几道黄牌去吧……
我们来看看动态加边的过程:
for(int i=1;i<=m;++i){
make_line(L[i].x,L[i].y,L[i].v1,L[i].v2);
spfa(L[i].x,L[i].y);
ans=min(ans,dis[n]+L[i].v1);
}
make_line(L[i].x,L[i].y,L[i].v1,L[i].v2); :
- 加边，不解释
spfa(L[i].x,L[i].y); :
– $Spfa$ 过程。
- $Q$ : 为什么要定义两个起点 $L[i].x$ 和 $L[i].y$ 呢？
$A$ : 显然加进来了这条边后，对当前图中一些点的 $dis$ 值可能会有影响，所以以这个边的两端的点为起点，依次更新旁边的点，直到不能再更新。
ans=min(ans,dis[n]+L[i].v1); :
– 更新 $ans$ 值
- $Q$ : 为什么使用 $dis[n]+L[i].v1$ 对 $ans$ 进行更新，有可能这条最短路上并不包含这个边啊，为什么要将 $L[i].v1$ 算进去呢？可能会更新错答案啊。
$A$ : 对于当前图的最短路，我们分两种情况来讨论：
- $1.$ 这条最短路上没包含这条新加上的边
- $2.$ 这条最短路上包含了这条新加上的边
- 对于第一种情况，显然这条最短路在加上这条边之前就已经有了，因为这条边的存在跟这条最短路没任何关系，既然之前有了，那么就肯定已经更新过 $ans$ 了。而那个时候的 $v1$ 是肯定比这个时候的 $v1$ 小的，也就是说 $ans$ 在之前已经被比现在的答案更小的答案更新过了，所以 $ans$ 也不会被当前答案更新。
对于第二种情况，因为这条最短路上包含了这条边，而这条边肯定是这条最短路上 $v1$ 最大的边 (当然也是当前图上 $v1$ 最大的边)，所以直接更新没错。
-
每一次循环后数组不要重置吗？
- 显然队列是不要的，因为 $Spfa$ 的退出条件是是队列为空，所以每次做完 $Spfa$ 时队列也就空了。
-
$vis$ 数组也不需要，跟队列是一个道理，只有 $vis$ 数组里面还有 $true$ 的元素，说明还有元素在队列里，队列空了，$vis$ 数组也自然空了。
-
$dis$ 数组不需要，因为循环中每次跑 $Spfa$ 是为了更新 $dis$ 数组而非做最短路。
然后…… 然后就没有然后了……
0 条评论