图的储存与遍历 -- 链式前向星存图 & 二分 & bfs F.简单图上操作

60 阅读 0 评论 40 点赞

我是靠谱客的博主高挑发箍，最近开发中收集的这篇文章主要介绍图的储存与遍历 -- 链式前向星存图 & 二分 & bfs F.简单图上操作，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：https://ac.nowcoder.com/acm/contest/2891/F
链接：https://ac.nowcoder.com/acm/contest/2891/F
来源：牛客网

题目描述
给一个n个站点m条边的无向图，每条边有边权，cat想出去玩，给出cat出发的起点s和旅行的终点t，cat背了一个容量为v的书包装有零食补充体力，如果有一条边距离超过v那么cat不能走这条边，因为他会体力不支走不动，每到一个站点cat都能买零食把书包重新填满，此外，cat还有k张万能车票，如果一条边距离超过v，它能使用一张车票坐车经过这条边，但是cat很懒不想背太重的书包，现在你来告诉它v最小可以设多少使得cat能顺利到达终点
输入描述:
第一行输入三个数n，m，k（1 <= n <=2e5，n - 1 <= m, k <= 4e5）

第二行输入两个数s,t，表示起点和终点（1 <= s, t <= n）

接下来m行输入三个数u, v, w代表u与v连接有一条距离为w的边（1 <= u, v <= n，1 <= w <= 1e9）
输出描述:
输出一个数表示答案
示例1
输入
复制
5 4 2
1 5
1 2 1
2 3 2
3 4 3
4 5 2
输出
复制
2
说明
提示：数据量较大，dfs小心爆栈，推荐链向星建图

链向星建图用法：

加边：
void add(int u, int v, int w) // u 连接一条边到 v，权值为w
{  
      Next[++cnt] = Laxt[u];
      Laxt[u] = cnt;
      To[cnt] = v;
      Len[cnt] = w;
}



清空：
void init()
{
       for (int i = 1; i <= n; i++)
        Laxt[i] = 0;
       cnt = 0;
 }



遍历：
for (int i = Laxt[u]; i; i = Next[i])
{
      int v = To[i];
     int w = Len[i];
}

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=(b);++i)
#define mem(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define pi pair<int, int>
#define mk make_pair
using namespace std;
typedef long long ll;
const int N=8e5+10,M=8e5+10;
bool vis[N];
int n,m,k,s,t,u,v,w;
int input(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
struct node
{
    int u,k;
    bool operator <(const node &o)const {
        k<o.k;
    }
};
struct edge
{
    int to,next,w;
}e[M];
int head[N],cnt;
void add_edge(int u,int v,int w)  //链式前向星存图
{
    e[++cnt]={v,head[u],w};
    head[u]=cnt;
}
int dis[N];
int bfs(int mid)
{
    for(int i=1;i<=n;++i)dis[i]=-1;
    queue<node>que;
    que.push({s,k});
    dis[s]=k;
    while(que.size()){
        node now=que.front();que.pop();
        if(now.u==t) return 1;
        for(int i=head[now.u];i;i=e[i].next){
            int v=e[i].to,w=e[i].w;
 
            if(w>mid){           //权值大于背包容量，用掉一张车票
                if(now.k>0&&dis[v]<now.k-1)
                {
                    dis[v]=now.k-1;   //dis[v]记录到v点还剩的车票数
                    que.push({v,dis[v]});
                }
            }
            else{
                if(dis[v]<now.k)    //权值小于背包容量，不需要用车票
                que.push({v,now.k}),dis[v]=now.k;
            }
        }
    }
    if(dis[t]>-1) return 1;
    return 0;
}
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
    int mx=0;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&u,&v,&w);
        mx=max(mx,w);
        add_edge(u,v,w);
        add_edge(v,u,w);
    }
    int l=0,r=mx;
    int ans=-1;
    while(l<=r)  //二分找答案
    {
        int mid=l+r>>1;
        if(bfs(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%dn",ans);
}
/*
7 8 1
1 6
1 2 100
2 3 100
2 4 99
4 5 99
5 3 99
3 6 100
4 7 88
7 6 88
*/