首页 > 代码库 > POJ2263&ZOJ1952--Heavy Cargo【Floyd】多源最短路变形
POJ2263&ZOJ1952--Heavy Cargo【Floyd】多源最短路变形
链接:http://poj.org/problem?id=2263
题意:有n个点,m条路,每条路双向的,现在卡车从某点到另一点,卡车的承载无上限,但是马路的承载有上限,问卡车应该承载多少才不会压坏马路。
poj2253和它类似,链接:http://poj.org/problem?id=2253
解题报告:Here
就是在两点之间找一条路径,使路径中权值最小的那条边的权值最大,edge数组记录当前路径中最小权值边的权值
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 510 #define eps 1e-7 #define INF 0x7FFFFFFF #define seed 131 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson r,m+1,rt<<1|1 map<string,int>mp; int edge[MAXN][MAXN]; int n,m,cnt; void floyd(){ int i,j,k; for(k=1;k<=cnt;k++){ for(i=1;i<=cnt;i++){ for(j=1;j<=cnt;j++){ edge[i][j] = max(edge[i][j],min(edge[i][k],edge[k][j])); } } } } int main(){ int k = 1,i,x; string str1,str2; while(scanf("%d%d",&n,&m),n||m){ if(!mp.empty()) mp.clear(); cnt = 0; memset(edge,0,sizeof(edge)); for(i=0;i<m;i++){ cin>>str1>>str2>>x; if(!mp[str1]) mp[str1] = ++cnt; if(!mp[str2]) mp[str2] = ++cnt; edge[mp[str1]][mp[str2]] = edge[mp[str2]][mp[str1]] = x; } floyd(); cin>>str1>>str2; printf("Scenario #%d\n",k++); printf("%d tons\n\n",edge[mp[str1]][mp[str2]]); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。