关于这道题目,我们可以抽象一下,即在保证货车不超过道路给定的最小限重量的情况下,使得货车装载的货物的重量最大。
即该边是一个顶点到另一个顶点所有路径中的最小的。
那么怎么去求解呢?具体请进我的另一篇博客:http://blog.csdn.net/wall_f/article/details/8177716
CODE:
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cstdlib> #include <map> using namespace std; const int MAXN = 220; const int INF = 0x3f3f3f3f; int d[MAXN][MAXN]; char str1[MAXN], str2[MAXN]; int tot; int n, m; map<string, int> my_map; void init() { tot = 0; for(int i = 1; i < MAXN; i++) // <= MAXN 又一次越界了。 { for(int j = 1; j < MAXN; j++) { d[i][j] = (i == j) ? INF : 0; } } my_map.clear(); } 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] = max(d[i][j], min(d[i][k], d[k][j])); } int main() { int times = 0; while(scanf("%d%d", &n, &m) && ( n || m)) { init(); while(m--) { int w; scanf("%s%s%d", str1, str2, &w); if(!my_map[str1]) my_map[str1] = ++tot; if(!my_map[str2]) my_map[str2] = ++tot; d[my_map[str1]][my_map[str2]] = d[my_map[str2]][my_map[str1]] = w; } Floyd(); scanf("%s%s", str1, str2); printf("Scenario #%d\n", ++times); printf("%d tons\n\n", d[my_map[str1]][my_map[str2]]); } return 0; }