最小瓶颈路&变形

自用笔记算法

最小瓶颈路&变形

基本概念&解法

瓶颈路：最小生成树的最大边
最小瓶颈路：A到B的所有路径中最大边的最小值
最小瓶颈路变形：A到B的所有路径中最小边的最大值

最小瓶颈路解法：
构造最小生成树确保最小值
对于单次询问 第一次用krusk把A点和B点的两个集合合并的路径就是所求
(因为kruskal的贪心策略确保第一个就是所求)
对于多次询问 用二维数组+LCA维护
最小瓶颈路变形：
构造最大生成树确保最大值
对于单次询问和多次询问如上

qwb与学姐

Description
qwb打算向学姐表白，可是学姐已经受够了他的骚扰，于是出了一个题想难住他:
已知一幅n个点m条边的无向图,定义路径的值为这条路径上最短的边的长度，
现在有 k个询问，
询问从A点到B点的所有路径的值的最大值。
qwb听完这个问题很绝望啊,聪明的你能帮帮他吗?

Input
一组数据。
第一行三个整数n，m，k (1<=N<=50000,m<=200000,k<=100000)。
第2..m+1行：三个正整数：X, Y, and D (1 <= X <=N; 1 <= Y <= N,1<=D<=215) 表示X与Y之间有一条长度为D的边。
第m+2..m+k+1行： 每行两个整数A B(1<=A,B<=n且A≠B)，意义如题目描述。
保证图连通。

Output
对于每个询问输出一行，一共k行，每行输出A点到B点的所有路径的值的最大值。

Sample Input
4 5 3
1 2 6
1 3 8
2 3 4
2 4 5
3 4 7
2 3
1 4
3 4

Sample Output
6
7
7

参考AC代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<bits/stdc++.h>
#define pb push_back
#define maxn 50050
using namespace std;
int n,m,k;
int dep[maxn],fa[20][maxn],mi[20][maxn];
int p[maxn];
struct node1{
    int u,v,w;
    bool operator < (const node1& p) const{
        return w>p.w;
    }
}e1[maxn<<2];
struct node2{
    int to,w;
    node2(int to,int w):to(to),w(w){}
};
vector<node2>e2[maxn];
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
}
void dfs(int x,int y){
    dep[x]=dep[y]+1;
    fa[0][x]=y;
    for(int i=1;fa[i-1][fa[i-1][x]];i++){
        fa[i][x]=fa[i-1][fa[i-1][x]];
        mi[i][x]=min(mi[i-1][x],mi[i-1][fa[i-1][x]]);
    }
    for(int i=0;i<e2[x].size();i++){
        int z=e2[x][i].to,w=e2[x][i].w;
        if(z==y)continue;
        mi[0][z]=w;
        dfs(z,x);
    }
}
int lca_mindist(int x,int y){
    int ret=1e9;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--)if(dep[fa[i][x]]>=dep[y])ret=min(ret,mi[i][x]),x=fa[i][x];
    if(x==y)return ret;
    for(int i=19;i>=0;i--){
        if(fa[i][x]!=fa[i][y]){
            ret=min(ret,mi[i][x]);
            ret=min(ret,mi[i][y]);
            x=fa[i][x];
            y=fa[i][y];
        }
    }
    ret=min(ret,mi[0][x]);
    ret=min(ret,mi[0][y]);
    return ret;
}
void kruskal(){
    for(int i=1;i<=n;i++) p[i]=i;
    sort(e1+1,e1+1+m);
    int cnt=0;
    for(int i=1;i<=m;i++){
        int x=find(e1[i].u),y=find(e1[i].v);
        if(x!=y){
            p[x]=y;
            e2[e1[i].u].pb(node2(e1[i].v,e1[i].w));
            e2[e1[i].v].pb(node2(e1[i].u,e1[i].w));
            if(++cnt==n-1) break;
        }
    }
} 
int main(){
//  freopen("input.txt","r",stdin);
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&e1[i].u,&e1[i].v,&e1[i].w);
    kruskal();
    dfs(1,0);
    while(k--){
        int x,y;
        scanf("%d%d",&x,&y);
        printf("%d\n",lca_mindist(x,y));
    }
    return 0;
}

思路

最小瓶颈路变形+多次询问

UVA 534

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1000
using namespace std;
struct node{
	int x,y;
}e[maxn];
struct node1{
	int u,v;
	double d;
	node1(int u,int v,double d):u(u),v(v),d(d){}
	bool operator < (const node1& p) const{
		return d<p.d;
	}
};
double dis(node a,node b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int p[maxn];
int n;
vector<node1>e1;
int find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
void kruskal(){
	for(int i=0;i<n;i++) p[i]=i;
	sort(e1.begin(),e1.end());
	for(int i=0;i<e1.size();i++){
		int x=find(e1[i].u),y=find(e1[i].v);
		if(x!=y){
			p[x]=y;
			if(find(0)==find(1)){
				printf("Frog Distance = %.3lf\n\n", e1[i].d);
				break;
			}
		}
	}
}
int flag=1;
int main(){
//	freopen("input.txt","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	while(cin>>n){
		if(n==0) break;
		e1.clear();
		printf("Scenario #%d\n", flag++);
		for(int i=0;i<n;i++) cin>>e[i].x>>e[i].y;
		for(int i=0;i<n;i++){
			for(int j=0;j<i;j++) e1.push_back(node1(i,j,dis(e[i],e[j])));
		}
		kruskal();
	}
	return 0;
}

思路

最小瓶颈路+单次询问

UVA 11354

参考AC代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define pb push_back
#define maxn 50050
using namespace std;
int n,m,k;
int dep[maxn],fa[20][maxn],mi[20][maxn];
int p[maxn];
struct node1{
	int u,v,w;
	bool operator < (const node1& p) const{
		return w<p.w;
	}
}e1[maxn<<2];
struct node2{
	int to,w;
	node2(int to,int w):to(to),w(w){}
};
vector<node2>e2[maxn];
void init(){
	for(int i=0;i<=n;i++) e2[i].clear();
	memset(e1,0,sizeof(e1));
	memset(dep,0,sizeof(dep));
	memset(fa,0,sizeof(fa));
	memset(mi,0,sizeof(mi));
}
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}
void dfs(int x,int y){
    dep[x]=dep[y]+1;
    fa[0][x]=y;
    for(int i=1;fa[i-1][fa[i-1][x]];i++){
        fa[i][x]=fa[i-1][fa[i-1][x]];
        mi[i][x]=max(mi[i-1][x],mi[i-1][fa[i-1][x]]);
    }
    for(int i=0;i<e2[x].size();i++){
        int z=e2[x][i].to,w=e2[x][i].w;
        if(z==y)continue;
        mi[0][z]=w;
        dfs(z,x);
    }
}
int lca_maxdist(int x,int y){
    int ret=-inf;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--)if(dep[fa[i][x]]>=dep[y])ret=max(ret,mi[i][x]),x=fa[i][x];
    if(x==y)return ret;
    for(int i=19;i>=0;i--){
        if(fa[i][x]!=fa[i][y]){
            ret=max(ret,mi[i][x]);
            ret=max(ret,mi[i][y]);
            x=fa[i][x];
            y=fa[i][y];
        }
    }
    ret=max(ret,mi[0][x]);
    ret=max(ret,mi[0][y]);
    return ret;
}
void kruskal(){
	for(int i=1;i<=n;i++) p[i]=i;
	sort(e1+1,e1+1+m);
	int cnt=0;
	for(int i=1;i<=m;i++){
		int x=find(e1[i].u),y=find(e1[i].v);
		if(x!=y){
			p[x]=y;
			e2[e1[i].u].pb(node2(e1[i].v,e1[i].w));
			e2[e1[i].v].pb(node2(e1[i].u,e1[i].w));
			if(++cnt==n-1) break;
		}
	}
} 
int flag=1;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		flag==1?flag++:printf("\n");
		init();
		for(int i=1;i<=m;i++) scanf("%d%d%d",&e1[i].u,&e1[i].v,&e1[i].w);
		kruskal();
		dfs(1,0);
		scanf("%d",&k);
		while(k--){
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",lca_maxdist(x,y));
		}	
	}
	return 0;
}

思路

最小瓶颈路+多次询问

uva 12655

题目要求

最小瓶颈路变形+多次询问

题目要求

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>
#define pb push_back
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define maxn 20050
#define maxm 100050
using namespace std;
int n,m,k;
int dep[maxn],fa[20][maxn],mi[20][maxn];
int p[maxm];
struct node1{
    int u,v,w;
    bool operator < (const node1& p) const{
        return w>p.w;
    }
}e1[maxm];
struct node2{
    int to,w;
    node2(int to,int w):to(to),w(w){}
};
vector<node2>e2[maxn];
void init(){
	for(int i=0;i<=n;i++) e2[i].clear();
	mm(e1,0),mm(dep,0),mm(fa,0),mm(mi,inf);
}
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
}
void dfs(int x,int y){
    dep[x]=dep[y]+1;
    fa[0][x]=y;
    for(int i=1;fa[i-1][fa[i-1][x]];i++){
        fa[i][x]=fa[i-1][fa[i-1][x]];
        mi[i][x]=min(mi[i-1][x],mi[i-1][fa[i-1][x]]);
    }
    for(int i=0;i<e2[x].size();i++){
        int z=e2[x][i].to,w=e2[x][i].w;
        if(z==y)continue;
        mi[0][z]=w;
        dfs(z,x);
    }
}
int lca_mindist(int x,int y){
    int ret=1e9;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=19;i>=0;i--)if(dep[fa[i][x]]>=dep[y])ret=min(ret,mi[i][x]),x=fa[i][x];
    if(x==y)return ret;
    for(int i=19;i>=0;i--){
        if(fa[i][x]!=fa[i][y]){
            ret=min(ret,mi[i][x]);
            ret=min(ret,mi[i][y]);
            x=fa[i][x];
            y=fa[i][y];
        }
    }
    ret=min(ret,mi[0][x]);
    ret=min(ret,mi[0][y]);
    return ret;
}
void kruskal(){
    for(int i=1;i<=n;i++) p[i]=i;
    sort(e1+1,e1+1+m);
    int cnt=0;
    for(int i=1;i<=m;i++){
        int x=find(e1[i].u),y=find(e1[i].v);
        if(x!=y){
            p[x]=y;
            e2[e1[i].u].pb(node2(e1[i].v,e1[i].w));
            e2[e1[i].v].pb(node2(e1[i].u,e1[i].w));
            if(++cnt==n-1) break;
        }
    }
} 
int main(){
//	freopen("input.txt","r",stdin);
    while(scanf("%d%d%d",&n,&m,&k)!=EOF){
    	init();
    	for(int i=1;i<=m;i++) scanf("%d%d%d",&e1[i].u,&e1[i].v,&e1[i].w);
	    kruskal();
	    dfs(1,0);
	    while(k--){
	        int x,y;
	        scanf("%d%d",&x,&y);
	        printf("%d\n",lca_mindist(x,y));
	    }	
	}
    return 0;
}

思路

跟本博客第一题相比 注意开边的大小 此题m为1e5

本文标题:最小瓶颈路&变形

文章作者:Hippopmonkey

发布时间:2017-06-11, 15:10:39

最后更新:2017-09-03, 22:29:01

原始链接:http://xuboming8.github.io/2017/06/11/最小瓶颈路-变形/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 最小瓶颈路&变形
    1. 1.1. 基本概念&解法
    2. 1.2. qwb与学姐
      1. 1.2.1. 参考AC代码
      2. 1.2.2. 思路
    3. 1.3. UVA 534
      1. 1.3.1. 参考AC代码
      2. 1.3.2. 思路
    4. 1.4. UVA 11354
      1. 1.4.1. 参考AC代码
      2. 1.4.2. 思路
    5. 1.5. uva 12655
      1. 1.5.1. 题目要求
      2. 1.5.2. 题目要求
      3. 1.5.3. 思路
|