中山品牌网站建设推广,南京网站设计制作公司排名榜,孝感网站的建设,做网站优化排名Description 给你一个无向图#xff0c;N(N500)个顶点, M(M5000)条边#xff0c;每条边有一个权值Vi(Vi30000)。给你两个顶点S和T #xff0c;求一条路径#xff0c;使得路径上最大边和最小边的比值最小。如果S和T之间没有路径#xff0c;输出”IMPOSSIBLE”N(N500)个顶点, M(M5000)条边每条边有一个权值Vi(Vi30000)。给你两个顶点S和T 求一条路径使得路径上最大边和最小边的比值最小。如果S和T之间没有路径输出”IMPOSSIBLE”否则输出 这个比值如果需要表示成一个既约分数。 备注 两个顶点之间可能有多条路径。 Input 第一行包含两个正整数N和M。下来的M行每行包含三个正整数xy和v。表示景点x到景点y之间有一条双向 公路车辆必须以速度v在该公路上行驶。最后一行包含两个正整数st表示想知道从景点s到景点t最大最小速 度比最小的路径。s和t不可能相同。 1N500,1x,yN0v300000M5000 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 题解 将所有边按权值排序枚举最小边顺序枚举最大边直到s和t连通。利用并查集。 没了。 附代码 #include algorithm
#include cstdio
typedef long long LL;
const int N 505, M 5050;
struct Edge{int u, v, w;bool operator(const Edge x)const{return w x.w;}
};
Edge e[M];
int fa[N];
int find(int x) {if (fa[x]) return fa[x] find(fa[x]);return x;
}
inline void Union(int x, int y) {if ((x find(x)) ! (y find(y)))fa[x] y;
}
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}
int main() {int n, m, s, t;scanf(%d%d, n, m);for (int i 0; i m; i)scanf(%d%d%d, e[i].u, e[i].v, e[i].w);std::sort(e, e m);scanf(%d%d, s, t);int ansn 10000000, ansd 1;for (int l 0; l 1 m; l) {for (int i 1; i n; i) fa[i] 0;Union(e[l].u, e[l].v);int r;for (r l 1; r m find(s) ! find(t); r)Union(e[r].u, e[r].v);if (find(s) find(t)) {int an e[r - 1].w, ad e[l].w;if ((LL)an * ansd (LL)ansn * ad)ansn an, ansd ad;}}if (ansn 10000000) return printf(IMPOSSIBLE), 0;int g gcd(ansn, ansd);ansn / g, ansd / g;printf(%d, ansn);if (ansd 1) printf(/%d, ansd);return 0;
}转载于:https://www.cnblogs.com/y-clever/p/6999313.html
