营救

题目背景

“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 $t$ 区，而自己在 $s$ 区。

该市有 $m$ 条大道连接 $n$ 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 $s$ 至 $t$ 的路线，使得经过道路的拥挤度最大值最小。

输入格式

第一行有四个用空格隔开的 $n$，$m$，$s$，$t$，其含义见【题目描述】。

接下来 $m$ 行，每行三个整数 $u,v,w$，表示有一条大道连接区 $u$ 和区 $v$，且拥挤度为 $w$。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数，代表最大的拥挤度。

样例 #1

样例输入 #1

3 3 1 3
1 2 2
2 3 1
1 3 3
1
2
3
4

样例输出 #1

2
1

#include
using namespace std;
typedef long long ll;
#define de(x) cout<<x<<" ";
#define sf(x) scanf("%d",&x);
#define Pu puts("");//最短路dijkstra做法
const int N=1e4+10,M=4e4+10;
struct E{
    int to,u;
};
int n,m,s,t;
int hed[N],nxt[M],var[M],u[M],tot;
int ans[N],vis[N];
void _add(int x,int y,int z){
    var[++tot]=y;
    nxt[tot]=hed[x];
    hed[x]=tot;
    u[tot]=z;
}
struct cmp{
    bool operator()(E a,E b){
        return a.u>b.u;
    }
};
priority_queue<E,vector<E>,cmp>q;
void dijkstra(){
    memset(ans,0x3f,sizeof(ans));
    q.push(E{s,0});ans[s]=0;
    int tw,tx,k;
    while(!q.empty()){
        tw=q.top().to;q.pop();
        if(vis[tw]) continue;
        vis[tw]=1;//和bfs不同，这里需要在弹出后给vis数组赋值
        //因为对于这个点，到达他可能会有很多条路径，而bfs边
        //的权重为1，先到达的为最优，可以直接标记
        for(int i=hed[tw];i;i=nxt[i]){
            tx=var[i];
            if(vis[tx]) continue;
            //int k=max(ans[tw],u[i]);
            if(u[i]>ans[tw]) k=u[i];
            else k=ans[tw];
            //对于x->y
            //找ans[x]和w[x->y]中的最大值，如果该值大于ans[y]
            //则说明这个值可以更新ans[y]

            if(ans[tx]>k){
                ans[tx]=k;
                q.push(E{tx,k});
            }
        }
    }
}
int main(){
    cin>>n>>m>>s>>t;
    int x,y,z;
    for(int i=1;i<=m;i++){
        sf(x)sf(y)sf(z)
        _add(x,y,z);
        _add(y,x,z);
    }
    dijkstra();
    printf("%d\n",ans[t]);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

#include
using namespace std;
typedef long long ll;
#define de(x) cout<<x<<" ";
#define sf(x) scanf("%d",&x);
#define Pu puts("");//最小生成树+并查集
const int N=1e4+10,M=4e4+10;
int n,m,s,t;
struct E{
    int x,y,u;
}e[M];
int ans;
int f[N];
int find(int x){
    if(x==f[x]) return x;
    return f[x]=find(f[x]);
}
bool cmp(E a,E b){
    return a.u<b.u;
}//从最小的边开始建树，保证得到的是最大值中的最大值
void fun(){
    for(int i=1;i<=n;i++) f[i]=i;
    int a,b;
    for(int i=1;i<=m;i++){
        a=find(e[i].x);b=find(e[i].y);
        if(a!=b){
            if(a>b) f[a]=b;
            else f[b]=a;
            //精髓，只要得到了下面break的条件，本题目就已经结束了
            //因为它是从小边开始的
            if(e[i].u>ans) ans=e[i].u;
            if(find(s)==find(t)||s==find(t)||find(s)==t) break;
            //注意这里要是find()函数，因为并查集只是更新了它的父亲
            //指向的点，它本身仍然指向它原来的父亲
        }
    }
}
int main(){
    cin>>n>>m>>s>>t;
    int x,y,z;
    for(int i=1;i<=m;i++){
        sf(x)sf(y)sf(z)//不用建双向边，因为并查集使得他们合一
        e[i].x=x;
        e[i].y=y;
        e[i].u=z;
    }
    sort(e+1,e+m+1,cmp);
    fun();
    printf("%d\n",ans);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51