P1396 营救

题目背景

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

题目描述

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

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

输入格式

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

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

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

输出格式

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

输入输出样例

输入 #1

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

输出 #1

1
2

方法一：先求出生成树，转有根树 （root = s）,从 t 往上计算最大边就是答案。

方法二：dij or spfa

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
const int MAX=10000+10;
int n,m,s,t,f[MAX],vis[MAX];
int fa[MAX],cost[MAX];
struct edge{
	int u,v,c;
	bool operator < (const edge &x) const{
		return c<x.c;
	}
}e[MAX*2];
int find(int x){
	return f[x]==-1?x:f[x]=find(f[x]);
}
struct edge2{
	int to,next,c;
}e2[MAX*2];
int head[MAX],tot=0;
void addedge(int u,int v,int c){
	e2[tot].to=v;
	e2[tot].c=c;
	e2[tot].next=head[u];
	head[u]=tot++;
}
void dfs(int u){
	vis[u]=1;
	for(int i=head[u];i!=-1;i=e2[i].next){
		int v= e2[i].to;
		if(vis[v]) continue;
		fa[v] = u;
		cost[v] = e2[i].c;
		dfs(v);
	}
}
int main(){
	freopen("in","r",stdin);
	mem(f,-1);mem(head,-1);
	sf(n);sf(m);sf(s);sf(t);
	fi(i,0,m){
		sf(e[i].u);sf(e[i].v);sf(e[i].c);
	}
	sort(e,e+m);
	fi(i,0,m){
		int u= find(e[i].u);
		int v= find(e[i].v);
		if(u!=v){
			f[u]=v;
			addedge(e[i].u,e[i].v,e[i].c);
			addedge(e[i].v,e[i].u,e[i].c);
		} 
	}
	dfs(s);
	int x = t,ans=0;
	while(x!=s){
		ans = max(ans,cost[x]);
		x=fa[x];
	}
	pf(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
//spfa 代码
const int MAX=10000+10;
int n,m,s,t,u,v,w,d[MAX];
struct edge{
	int to,next,c;
}e[MAX*2*2];
int head[MAX],tot=0;
void addedge(int u,int v,int c){
	e[tot].to=v;
	e[tot].c=c;
	e[tot].next=head[u];
	head[u]=tot++;
}
void spfa(int s){
	queue<int> q;
	bool inq[MAX];
	mem(inq,0);
	mem(d,0x3f);
	q.push(s);
	d[s]=0;
	while(!q.empty()){
		int u= q.front();
		q.pop();
		inq[u]=0;
		for(int i=head[u];i!=-1;i=e[i].next){
			int v=e[i].to;
			if(d[v]>max(d[u],e[i].c)){ //松弛
				d[v]=max(d[u],e[i].c);
				if(!inq[v]){
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main(){
	freopen("in","r",stdin);
	mem(head,-1);
	sf(n);sf(m);sf(s);sf(t);
	fi(i,0,m){
		sf(u);sf(v);sf(w);
		addedge(u,v,w);addedge(v,u,w);
	}
	spfa(s);
	pf(d[t]);
	return 0;
}