問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=2263思路:
這題，我自己的想法是更像DP，設(shè)源點(diǎn)是source，d[i]表示從source到頂點(diǎn)i的每條路徑中的最小值的最大值，即該題要求的結(jié)果
d[i] = max (d[i], min(d[k], adj[k][i]))，其中頂點(diǎn)k是從source到頂點(diǎn)i的路徑中頂點(diǎn)i的前趨
具體編程的話，更像是Dijkstra的方式，只不過這里所有的頂點(diǎn)都必須更新
另外，這題還用到了字符串哈希，來將每個頂點(diǎn)用一個整數(shù)表示
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_N 201
5 #define MAX_LEN 31
6 #define INF 0x7FFFFFFF
7 #define HASH_LEN 19999
8 #define Min(a, b) ((a)<(b) ? (a) : (b))
9 #define Max(a, b) ((a)<(b) ? (b) : (a))
10 int n, r, hash_val;
11 int from, to, adj[MAX_N][MAX_N];
12 int d[MAX_N], in[MAX_N];
13 struct City{
14 char name[MAX_LEN];
15 int num;
16 } cities[MAX_N];
17 struct Node {
18 int index;
19 struct Node *next;
20 };
21 struct Node *hash[HASH_LEN] = {NULL};
22
23 int ELFHash(char *str)
24 {
25 unsigned long t, hash = 0;
26 while(*str) {
27 hash = (hash<<4) + (*str++);
28 if((t = hash&0xF0000000L))
29 hash ^= t>>24;
30 hash &= ~t;
31 }
32 return (hash & 0x7FFFFFFF)%HASH_LEN;
33 }
34
35 void
36 insert(int index)
37 {
38 struct Node *node = (struct Node *)malloc(sizeof(struct Node));
39 node->index = index;
40 node->next = hash[hash_val];
41 hash[hash_val] = node;
42 }
43
44 int
45 search(char *str)
46 {
47 struct Node *node = hash[hash_val];
48 while(node != NULL) {
49 if(strcmp(str, cities[node->index].name) == 0)
50 return cities[node->index].num;
51 node = node->next;
52 }
53 return -1;
54 }
55
56 void
57 init()
58 {
59 int i, j, mark, f, t, c;
60 char str[MAX_LEN];
61 memset(hash, 0, sizeof(hash));
62 memset(adj, 0, sizeof(adj));
63 for(j=0, mark=1, i=0; i<r; i++) {
64 scanf("%s", cities[j].name);
65 hash_val = ELFHash(cities[j].name);
66 if((f=search(cities[j].name)) == -1) {
67 insert(j);
68 cities[j].num = mark++;
69 f = cities[j].num;
70 j++;
71 }
72 scanf("%s", cities[j].name);
73 hash_val = ELFHash(cities[j].name);
74 if((t=search(cities[j].name)) == -1) {
75 insert(j);
76 cities[j].num = mark++;
77 t = cities[j].num;
78 j++;
79 }
80 scanf("%d", &c);
81 if(adj[f][t] < c)
82 adj[f][t] = adj[t][f] = c;
83 }
84 scanf("%s", str);
85 hash_val = ELFHash(str);
86 from = search(str);
87 scanf("%s", str);
88 hash_val = ELFHash(str);
89 to = search(str);
90 }
91
92 void
93 solve()
94 {
95 int i, j, k, tmp;
96 memset(in, 0, sizeof(in));
97 for(i=1; i<=n; i++)
98 d[i] = 0;
99 d[from] = INF;
100 in[from] = 1;
101 for(i=1; i<=n; i++) {
102 if(adj[from][i])
103 d[i] = adj[from][i];
104 }
105
106 k = n-1;
107 while(k > 0) {
108 for(i=1; i<=n; i++) {
109 if(!in[i] && d[i]!=0) {
110 for(j=1; j<=n; j++) {
111 if(adj[i][j]) {
112 tmp = Min(d[i], adj[i][j]);
113 d[j] = Max(d[j], tmp);
114 }
115 }
116 in[i] = 1;
117 --k;
118 }
119 }
120 }
121 }
122
123 int
124 main(int argc, char **argv)
125 {
126 int tests = 0;
127 while(scanf("%d %d", &n, &r) != EOF) {
128 if(n==0 && r==0)
129 break;
130 init();
131 solve();
132 printf("Scenario #%d\n%d tons\n\n", ++tests, d[to]);
133 }
134 }