【二分dfs / 生成树 / SPFA】P1396 营救

· · 个人记录

P1396 营救

一、SPFA

显然的，从s到t拥挤度最小的最大值应该是经由x到t，值为3。

既然要松驰，第一时间想到最短路算法。

但本题显然不是取最短路。设dis[t]=4，显然中转算法应该是：

min(4,max(3,2))，因此只需要修改SPFA的松驰代码为：

if(dis[v]>max(dis[u],w[x]) dis[v]=max(dis[u],w[x]) 即可。

#include <bits/stdc++.h>
using namespace std;

struct edge {
    int u,v,w,next; 
} e[50005];
int vex[10005],dis[10005],vis[10005],que[50005],head=0,rear=0;
int n,m,s,t;

int spfa(int s,int t){
    for(int i=1;i<=n;i++) dis[i]=1e9;
    dis[s]=0;
    que[rear++]=s;
    while(head<rear){
        vis[que[head]]=0;
        for(int i=vex[que[head]];i;i=e[i].next){
            int d=max(dis[que[head]],e[i].w);//关键代码
            if(d<dis[e[i].v]){//关键代码
                dis[e[i].v]=d;
                if(!vis[e[i].v]){
                    que[rear++]=e[i].v;
                    vis[e[i].v]=1;
                }
            }
        }
        head++;
    }
    return dis[t];
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>e[i].u>>e[i].v>>e[i].w;
        e[i].next=vex[e[i].u];
        vex[e[i].u]=i;
        e[m+i].u=e[i].v;
        e[m+i].v=e[i].u;
        e[m+i].w=e[i].w;
        e[m+i].next=vex[e[i].v];
        vex[e[i].v]=i+m;
    }
    cout<<spfa(s,t);
    return 0;
}

二、最小生成树

换种思维，要使拥挤度较小，我们优先选取最小边，逐渐增大，直到s和t连通，这不是最小生成树吗？

#include <bits/stdc++.h>
using namespace std;

struct edge {
    int u,v,w;  
} e[50005];
int pre[10005],k,n;

int cmp(edge a,edge b){
    return a.w<b.w;
}

void add(int u,int v,int w){
    k++;
    e[k].u=u;
    e[k].v=v;
    e[k].w=w;
    return;
}

int Find(int x){
    if(pre[x]==x) return x;
    return pre[x]=Find(pre[x]);
}

int mst(int s,int t){
    for(int i=1;i<=n;i++) pre[i]=i;
    sort(e+1,e+k+1,cmp);
    for(int i=1;i<=k;i++){
        int u=Find(e[i].u),v=Find(e[i].v);
        if(u!=v){
            pre[u]=v;
            //s和t连通，可以中止了，此边就是最大边
            if(Find(s)==Find(t)) return e[i].w;
        }
    }
    return -1;
}

int main(){
    int u,v,w,m,s,t;
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
    }
    cout<<mst(s,t); 
    return 0;
}

三、二分+dfs

最小的最大值，二分！我们猜一个答案，比答案大的边不能走，如果还能走到终点，说明答案大了，否则答案小了。

#include <bits/stdc++.h>
using namespace std;

struct edge {
    int u,v,w,next;
} e[50005];
int k,n,f,vis[10005],vex[10005],s,t;

void add(int u,int v,int w) {
    k++;
    e[k].u=u;
    e[k].v=v;
    e[k].w=w;
    e[k].next=vex[u];
    vex[u]=k;
    return;
}

void dfs(int u,int mid) {
    if(vis[u]||f) return;
    vis[u]=1;
    if(u==t) { //到终点，标记，强制中止dfs
        f=1;
        return;
    }
    for(int i=vex[u]; i; i=e[i].next) {
        //比mid大的边不能走
        if(e[i].w<=mid) dfs(e[i].v,mid);
    }
    return;
}

int check(int mid) {
    f=0;
    memset(vis,0,sizeof(vis));
    dfs(s,mid);
    return !f;
}

int main() {
    int u,v,w,m;
    cin>>n>>m>>s>>t;
    for(int i=1; i<=m; i++) {
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    int l=1,r=10000,mid;
    while(l<=r) {
        mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<l;
    return 0;
}