给你一个无向图,N(N<=500)个顶点, M(M<=5000)条边,每条边有一个权值Vi(Vi<30000)。给你两个顶点S和T,求
一条路径,使得路径上最大边和最小边的比值最小。如果S和T之间没有路径,输出”IMPOSSIBLE”,否则输出这个
比值,如果需要,表示成一个既约分数。 备注: 两个顶点之间可能有多条路径。
镜龙战全文阅读,贺捷生,澳元汇率走势
考虑到$N, M$很小,所以考虑$(N/M)^2$级别的算法
刚开始我很zz的认为答案在最小/最大生成树上,
然而
1 2 2
2 3 4
1 3 5
这组数据就可以卡掉。
考虑如何解决这种问题。
我们可以枚举最小值所在的边,然后把比他权值大的边往上加。如果S和T联通了就退出
这样肯定是对的。
时间复杂度$O(M^2)$
#include<cstdio> #include<algorithm> #define LL long long const int MAXN = 1e5 + 10, INF = 1e9 + 10; using namespace std; inline int read() { char c = getchar();int x = 0,f = 1; while(c < '0' || c > '9'){if(c == '-')f = -1;c = getchar();} while(c >= '0' && c <= '9'){x = x * 10 + c - '0',c = getchar();} return x * f; } struct Edge { int u, v, w; bool operator < (const Edge &rhs) const { return w < rhs.w; } }E[MAXN]; int N, M, fa[MAXN], S, T; int find(int x) { if(fa[x] == x) return fa[x]; else return fa[x] = find(fa[x]); } int Build(int now) { int mx = -INF, tot = 0; for(int i = 1; i <= N; i++) fa[i] = i; for(int i = now; i <= M; i++) { int fx = find(E[i].u), fy = find(E[i].v); if(fx == fy) continue; tot++; fa[fx] = fy; mx = max(mx, E[i].w); if(find(S) == find(T)) return mx; } return INF; } main() { N = read(); M = read(); for(int i = 1; i <= M; i++) { int x = read(), y = read(), z = read(); E[i] = (Edge){x, y, z}; } S = read(), T = read(); sort(E + 1, E + M + 1); double now = INF; int mi = INF, mx = INF; for(int i = 1; i <= M; i++) { int nowx = Build(i); if((double)nowx / E[i].w < now) { mi = E[i].w, mx = nowx; now = (double)mx / mi; } } if(mx == INF) printf("IMPOSSIBLE"); else { int gcd = __gcd(mi, mx); if(mi / gcd != 1) printf("%d/%d", mx / gcd, mi / gcd); else printf("%d", mx / gcd); } }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论