旅行 comf
给你一个无向图, N(N<=500) 个顶点, M(M<=5000) 条边, 每条边有一个权值 Vi(Vi<30000). 给你两个顶点 S 和 T, 求一条路径, 使得路径上最大边和最小边的比值最小. 如果 S 和 T 之间没有路径, 输出 "IMPOSSIBLE", 否则输出这个比值, 如果需要, 表示成一个既约分数. 备注: 两个顶点之间可能有多条路径.
Input
第一行包含两个正整数, N 和 M. 下来的 M 行每行包含三个正整数: x,y 和 v. 表示景点 x 到景点 y 之间有一条双向公路, 车辆必须以速度 v 在该公路上行驶. 最后一行包含两个正整数 s,t, 表示想知道从景点 s 到景点 t 最大最小速度比最小的路径. s 和 t 不可能相同. 1<N<=500,1<=x,y<=N,0<v<30000,0<M<=5000
Output
如果景点 s 到景点 t 没有路径, 输出 "IMPOSSIBLE". 否则输出一个数, 表示最小的速度比.
如果需要, 输出一个既约分数.
Sample Input
[样例输入 1]
- 4 2
- 1 2 1
- 3 4 2
- 1 4
[样例输入 2]
- 3 3
- 1 2 10
- 1 2 5
- 2 3 8
- 1 3
[样例输入 3]
- 3 2
- 1 2 2
- 2 3 4
- 1 3
- Sample Output
[样例输出 1]
IMPOSSIBLE
[样例输出 2]
5/4
[样例输出 3]
2
解题思路:
本题给出景点数量 n, 道路数量 m, 之后给出 m 行, 每行包括三个整数, 分别为道路两端的景点, x,y 与该道路的行驶速度 v, 下一行为两个整数, 分别为起始景点 s, 目标景点 t, 如果 s 与 t 之间连通, 就选择一条道路使从 s 到达 t 的最小速度比最大, 输出其最大边和最小边的比值的最小值的最简分数形式, 若不连通, 输出 IMPOSSIBLE.
本题最小速度比是指一条道路上最大的速度与最小的速度的比值最小. 且我们首先思考如何找到一条连通 s 与 t 道路上的最大边与最小边, 怎么办? 最小生成树! 克鲁斯卡尔!
kruskal 算法核心思想:
既然已经给出了邻接表. 将道路按速度由小到大排序, 枚举最小速度, 初始视所有景点都为不连通, 之后由最小速度的道路开始以速度从小到大枚举所有道路, 判断道路两端的景点是否已经连通, 若已经连通不做处理, 若不连通则将该道路记录入最小生成树, 标记道路两端为连通, 判断 s 与 t 是否连通, 若连通标记 s 与 t 可达, 计算此时的最大速度与最小速度比值 (因为道路速度由小到大遍历所以最小速度为开始遍历时的道路速度, 最大速度为当前道路速度), 将现在的比值与之前记录的比值比较, 如果现在的值小于先前的值, 将比值记录为现在的比值, 并记录这时的最大速度与最小速度.
- bool kruskal(int n, int m, int s, int t, int &maxL, int &minL){
- // 传入的 n 为景点数量, m 为道路数量, s 为起点, t 为目标景点
- // 由于要改变 maxL 与 minL 记录最终的最大值与最小值, 所以 maxL 与 minL 传引用
- double ans = inf; // 初始化比值为无穷大
- bool flag = false; // 标记 s 与 t 为不可达
- sort(Edge + 1, Edge + 1 + m, cmp); // 将道路由小到大排序
- for(int i = 1; i <= m; i++){ // 枚举最小速度
- for(int k = 1; k <= n; k++){ // 初始化所有景点为不连通
- father[k] = k;
- }
- int minlen = Edge[i].v, maxlen = 0; // 记录最小速度, 初始化最大速度为 0
- for(int j = i; j <= m; j++){ // 以速度由小到大枚举所有道路
- int faNode1 = getFather(Edge[j].node1);
- int faNode2 = getFather(Edge[j].node2);
- maxlen = Edge[j].v; // 记录最大速度为当前道路速度
- if(faNode1 != faNode2){ // 判断道路两端顶点是否连通
- father[faNode1] = faNode2; // 不连通就标记为连通
- if(getFather(s) == getFather(t)){ // 判断 s 与 t 是否连通
- flag = true; // 如果连通标记 s 与 t 为可达
- if(ans> (double)maxlen / minlen){
- // 计算此时的最大速度与最小速度比值, 将现在的比值与之前记录的比值比较
- ans = (double)maxlen / minlen;
- // 如果现在的值小于先前的值, 将比值记录为现在的比值
- maxL = maxlen;
- minL = minlen;
- // 记录这时的最大速度与最小速度
- break;
- }
- }
- }
- }
- }
- if(flag){ // 如果 s 与 t 可达返回 true, 否则返回 false
- return true;
- }else{
- return false;
- }
- }
- kruskal
是否连通用并查集进行判断
- int father[maxn], maxL, minL; // 并查集部分
- int getFather(int x)
- {
- if(father[x] == x)
- return x;
- else
- return father[x] = getFather(father[x]);
- }
并查集
AC 代码
- #include <bits/stdc++.h>
- using namespace std;
- const int inf = 0x7fffffff; // 无穷大
- const int maxn = 3e4+10;
- struct edge{ //edge 保存道路
- int node1, node2; // 道路两端景点
- int v; // 道路速度
- }Edge[maxn];
- int gcd(int a, int b){ // 计算最大公约数
- if(b == 0)
- return a;
- else
- return gcd( b, a % b);
- }
- bool cmp(edge e1, edge e2){ // 道路按速度由小到大排序
- return e1.v <e2.v;
- }
- int father[maxn], maxL, minL; // 并查集部分
- int getFather(int x)
- {
- if(father[x] == x)
- return x;
- else
- return father[x] = getFather(father[x]);
- }
- bool kruskal(int n, int m, int s, int t, int &maxL, int &minL){
- // 传入的 n 为景点数量, m 为道路数量, s 为起点, t 为目标景点
- // 由于要改变 maxL 与 minL 记录最终的最大值与最小值, 所以 maxL 与 minL 传引用
- double ans = inf; // 初始化比值为无穷大
- bool flag = false; // 标记 s 与 t 为不可达
- sort(Edge + 1, Edge + 1 + m, cmp); // 将道路由小到大排序
- for(int i = 1; i <= m; i++){ // 枚举最小速度
- for(int k = 1; k <= n; k++){ // 初始化所有景点为不连通
- father[k] = k;
- }
- int minlen = Edge[i].v, maxlen = 0; // 记录最小速度, 初始化最大速度为 0
- for(int j = i; j <= m; j++){ // 以速度由小到大枚举所有道路
- int faNode1 = getFather(Edge[j].node1);
- int faNode2 = getFather(Edge[j].node2);
- maxlen = Edge[j].v; // 记录最大速度为当前道路速度
- if(faNode1 != faNode2){ // 判断道路两端顶点是否连通
- father[faNode1] = faNode2; // 不连通就标记为连通
- if(getFather(s) == getFather(t)){ // 判断 s 与 t 是否连通
- flag = true; // 如果连通标记 s 与 t 为可达
- if(ans> (double)maxlen / minlen){
- // 计算此时的最大速度与最小速度比值, 将现在的比值与之前记录的比值比较
- ans = (double)maxlen / minlen;
- // 如果现在的值小于先前的值, 将比值记录为现在的比值
- maxL = maxlen;
- minL = minlen;
- // 记录这时的最大速度与最小速度
- break;
- }
- }
- }
- }
- }
- if(flag){ // 如果 s 与 t 可达返回 true, 否则返回 false
- return true;
- }else{
- return false;
- }
- }
- int main()
- {
- int numNode, numEdge;
- while(scanf("%d%d", &numNode, &numEdge)!= EOF){ // 输入景点数与道路数
- for(int i = 1; i <= numEdge; i++){ // 输入道路
- scanf("%d%d%d", &Edge[i].node1, &Edge[i].node2, &Edge[i].cost);
- }
- int s, t;
- scanf("%d%d", &s, &t); // 输入起点终点
- int maxL = 0;
- int minL = 0;
- // 初始化最大最小速度都为 0
- if(kruskal(numNode, numEdge, s, t, maxL, minL)){ // 如果 s 与 t 连通
- int temp = gcd(maxL, minL); // 计算最大最小速度的最大公约数
- //printf("%d\n", gcd(maxL, minL));
- int a = maxL/temp, b = minL/temp; // 计算分子分母
- if(b != 1) // 分子不等于 1 输出最简分数
- printf("%d/%d\n", a, b);
- else
- printf("%d\n", a); // 分子为 1 直接输出分母
- }else{ // 不连通输出 IMPOSSIBLE
- printf("IMPOSSIBLE\n");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2848838.html