膜法森林 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$ 数组而非做最短路

然后…… 然后就没有然后了……

分类: 文章

Qiuly

井戸の底の空にはまだかすかな希望の光がある……

发表评论

电子邮件地址不会被公开。 必填项已用*标注