Problem Solving►UVa

UVa 544 - Heavy Cargo

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

p.s. 路徑中最小的那個才是整段路的最大負載重量

Solution

直接做 SPFA 找最大負載重量。

判斷式 : 

int maxW = weight[u] ? MIN(adjM[u][v], weight[u]) : adjM[u][v];

weight[u] 等於零時表還沒計算過，所以直接等於 adjM[u][v] 即可。
兩段路 (st->u->v) 中可負載的最大為，兩段中較小的。

Code

UVa 544
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<iostream>
#include<queue>
#include<map>
#include<string>
#define MIN(a,b) ((a)<(b)?(a):(b))
#define N 201
using namespace std;

int adjM[N][N] = {};
int SPFA(int n, int st, int end);
int main()
{
    int n, r, i, j, Case = 1;

    while (scanf("%d%d", &n, &r) && n)
    {
        map<string, int> city;
        string str1, str2;
        int count = 0, a, b, w;
        for (i = 0; i <= n; i++)
            for (j = 0; j <= n; j++)
                adjM[i][j] = 0;

        for (i = 0; i < r; i++)
        {
            cin >> str1 >> str2 >> w;
            if (!city.count(str1))
                city[str1] = ++count;
            if (!city.count(str2))
                city[str2] = ++count;

            a = city[str1];
            b = city[str2];

            adjM[b][a] = adjM[a][b] = w;
        }

        cin >> str1 >> str2;
        printf("Scenario #%d\n", Case++);
        printf("%d tons\n\n", SPFA(n, city[str1], city[str2]));
    }

    return 0;
}
int SPFA(int n, int st, int end)
{
    queue<int> Q;
    int weight[N] = {};
    bool inQ[N] = {};
    Q.push(st);

    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        inQ[u] = false;

        for (int v = 1; v <= n; v++)
            if (adjM[u][v])
            {
                int maxW = weight[u] ? MIN(adjM[u][v], weight[u]) : adjM[u][v];//兩段路 (st->u->v) 中可負載的最大為，兩段中較小的

                if (maxW > weight[v])//看似否比原先路段 (st->v) 中的負載能力高
                {
                    weight[v] = maxW;
                    if (!inQ[v])
                    {
                        Q.push(v);
                        inQ[v] = true;
                    }
                }
            }
    }

    return weight[end];
}