两道以Floyd算法为解法的范例，第二题如果数据量较大，须采用其他解法
POJ2570-Fiber Network
//经典的传递闭包问题，由于只有26个公司可以采用二进制存储//Time:141Ms Memory:328K#include#include #include using namespace std;#define MAX 205#define MAXS 28int n;int d[MAX][MAX];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] |= d[i][k] & d[k][j]; //找出两条线路的相同公司}int main(){ while (scanf("%d", &n), n) { memset(d, 0, sizeof(d)); int a, b; char s[MAXS]; while (scanf("%d%d", &a, &b), a && b) { scanf("%s", s); int len = strlen(s); for (int i = 0; i < len; i++) d[a][b] |= 1 << (s[i] - 'a'); } floyd(); while (scanf("%d%d", &a, &b), a && b) { if (d[a][b] == 0) printf("-\n"); else { int tmp = d[a][b]; for (int i = 0; i < 26; i++, tmp >>= 1) if (tmp & 1) putchar('a' + i); //单个字符输出putchar较快 printf("\n"); } } printf("\n"); } return 0;}
POJ2263-Heavy Cargo
//求图中起点到终点的公路最大承载量//Time:32Ms Memory:500K#include#include #include #include using namespace std;#define MAX 205#define MAXS 32struct City { char s[MAXS];}c[MAX];int n, m;int lc;int board[MAX][MAX];int d[MAX][MAX];int find(char s[MAXS]){ for (int i = 0; i < lc; i++) if (!strcmp(s, c[i].s)) return i; return -1;}void floyd(){ memcpy(d, board, sizeof(board)); for (int k = 0; k < lc; k++) for (int i = 0; i < lc; i++) for (int j = 0; j < lc; j++) d[i][j] = max(d[i][j], min(d[i][k], d[k][j]));}int main(){ int cas = 0; while (scanf("%d%d", &n, &m), n && m) { int dis; lc = 0; memset(board, -1, sizeof(board)); for (int i = 0; i < m; i++) { scanf("%s%s%d", c[lc].s, c[lc+1].s, &dis); int n1 = find(c[lc].s); int n2 = find(c[lc + 1].s); if (n1 == -1) { n1 = lc++; if (n2 == -1) n2 = lc++; } else if (n2 == -1) c[n2 = lc++] = c[lc + 1]; board[n1][n2] = board[n2][n1] = dis; } char s1[MAXS], s2[MAXS]; scanf("%s%s", s1, s2); int n1 = find(s1); int n2 = find(s2); floyd(); printf("Scenario #%d\n", ++cas); printf("%d tons\n\n", d[n1][n2]); } return 0;}