首页 > 代码库 > uva 10048 - Audiophobia(floyd 的变形)
uva 10048 - Audiophobia(floyd 的变形)
给出一个无向连通图以及边权,目的求从一个点到另一个点的路径中 边权最大值 最小的那条路径,输出的是该条路径的最大边权。
因为是两点间路径问题,且数据量很小(只有100个) ,所以考虑使用floyd算法。
但是要求的并不是传统 floyd 所求的 两点之间最短路 问题,但是通过理解floyd算法的原理,可以发现floyd的思想可以用来解决这种问题:
对于任何一条至少包含两条边的路径i->j,一定存在一个中间点k,使得i->j的总长度等于i->k与k->j的长度之和。因为路径可能有多个,所以最后需要取最小值。
对于任何一条至少包含两条边的路径i->j,一定存在一个中间点k,使得i->j的 最大权值 等于i->k与k->j的 最大权值 。因为路径可能有多个,所以最后需要取最小值。
就是上面这个道理。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define INF 0x3fffffff #define mem(a) memset(a,0,sizeof(a)) int n,s,q; int d[105][105]; void floyd(){ for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ d[i][j]=min(d[i][j],max(d[i][k],d[k][j])); } } } } int main() { // freopen("out.txt","w",stdout); int kase=1; while(scanf("%d%d%d",&n,&s,&q)!=EOF) { if(n==0&&s==0&&q==0) break; mem(d); for(int i=0;i<=n;i++){ for(int j=0;j<=n;j++) d[i][j]=INF; } int a1,a2,a3; for(int i=0;i<s;i++){ scanf("%d%d%d",&a1,&a2,&a3); d[a1][a2]=a3; d[a2][a1]=a3; } floyd(); if(kase!=1) printf("\n"); printf("Case #%d\n",kase++); for(int i=0;i<q;i++) { int u,v; scanf("%d%d",&u,&v); if(d[u][v]==INF) printf("no path\n"); else printf("%d\n",d[u][v]); } } return 0; }
uva 10048 - Audiophobia(floyd 的变形)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。