PAT「1003 Universal Travel Sites (35分)」

1. 题目

题目链接：PAT「1003 Universal Travel Sites (35分)」 。

Description

After finishing her tour around the Earth, CYLL is now planning a universal travel sites development project. After a careful investigation, she has a list of capacities of all the satellite transportation stations in hand. To estimate a budget, she must know the minimum capacity that a planet station must have to guarantee that every space vessel can dock and download its passengers on arrival.

Input Specification:

Each input file contains one test case. For each case, the first line contains the names of the source and the destination planets, and a positive integer NN (≤500\leq 500). Then NN lines follow, each in the format: source[i] destination[i] capacity[i] where source[i] and destination[i] are the names of the satellites and the two involved planets, and capacity[i] >0> 0 is the maximum number of passengers that can be transported at one pass from source[i] to destination[i]. Each name is a string of 33 uppercase characters chosen from {A-Z}, e.g., ZJU.

Note that the satellite transportation stations have no accommodation facilities for the passengers. Therefore none of the passengers can stay. Such a station will not allow arrivals of space vessels that contain more than its own capacity. It is guaranteed that the list contains neither the routes to the source planet nor that from the destination planet.

Output Specification:

For each test case, just print in one line the minimum capacity that a planet station must have to guarantee that every space vessel can dock and download its passengers on arrival.

Sample Input:

1
2
3
4
5
6
7
8
9
10
11
12
EAR MAR 11
EAR AAA 300
EAR BBB 400
AAA BBB 100
AAA CCC 400
AAA MAR 300
BBB DDD 400
AAA DDD 400
DDD AAA 100
CCC MAR 400
DDD CCC 200
DDD MAR 300

Sample Output:

1
700

2. 题解

分析

很明显的一道网络流题，可以直接上网络流的板子，但是蒟蒻的我，竟然把网络流的板子给忘了，连带那些算法也想不起来了 😦 真菜。只好暴力推流。从起始节点开始，对每个节点的出边使用 dfs 向其后续节点推流，直到推到终止节点，对于当前节点推不过去的流量要返还给父节点。由于可能有环，所以需要对每个节点进行标记，如果当前节点在当前一次推流过程中被访问过，就标记以下，如果推流结束（即逆向返还剩余流时）就取消标记。最终暴力 AC（这都没有 TLE，PAT 上的测试数据真的太弱了！）。

代码

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 505, INF = 0x3f3f3f3f;

unordered_map < string, int > ump;

// 前向星存边
typedef struct {
    int to, next, capability;
}edge;

int n;
int len_e;
int c[MAXN];
int h[MAXN];
int f[MAXN];
edge e[MAXN];

// 初始化节点
void init(int n) {
    for(int i = n-1; ~i; --i) {
        h[i] = -1;
    }
}

// 新增边
void add(int x, int y, int v) {
    e[len_e].next = h[x];
    e[len_e].to = y;
    e[len_e].capability = v;
    h[x] = len_e++;
}

// 推流
int update(int x, int v) {
    if(x == 1) {
        return 0;
    }
    for(int i = h[x]; i != -1 && v; i = e[i].next) {
        if(f[e[i].to] || e[i].capability == 0)    continue;
        f[e[i].to] = 1;
        int s, t;
        if(e[i].capability >= v) {
            s = update(e[i].to, v);
            t = v-s;
        } else {
            s = update(e[i].to, e[i].capability);
            t = e[i].capability-s;
        }
        v -= t;
        c[e[i].to] += t;
        e[i].capability -= t;
        f[e[i].to] = 0;
    }
    return v;
}

int answer() {
    c[0] = INF;
    for(int i = h[0]; i != -1; i = e[i].next) {
        memset(f, 0, sizeof(f));
        f[e[i].to] = 1;
        int s = update(e[i].to, e[i].capability);
        int t = e[i].capability - s;
        c[e[i].to] += t;
        e[i].capability -= t; 
        f[e[i].to] = 0;
    }
    return c[1];
}

int main() 
{
    char s[4], t[4];
    int m;
    scanf("%s%s%d", s, t, &m);
    ump[s] = n++;
    ump[t] = n++;
    init(MAXN);
    for(int i = m; i; --i) {
        char ts[4], tv[4];
        int tst, tvt, cap;
        scanf("%s%s%d", ts, tv, &cap);
        if(ump.count(ts) == 0) {
            ump[ts] = n++;
        }
        if(ump.count(tv) == 0) {
            ump[tv] = n++;
        }
        tst = ump[ts];
        tvt = ump[tv];
        add(tst, tvt, cap);
    }
    printf("%d\n", answer());
    return 0;
}

附录

  • Dinic 算法

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <bits/stdc++.h>
using namespace std;

// Dinic 算法
struct Dinic {
    #ifndef _DINIC_
    #define ll long long 
    #define MAXN 1505
    #define MAXM 1505
    #define INF 1e12
    #endif
    
    ll cnt_edge;    // 边数
    ll head[MAXN];  // 节点的第一条边的编号
    ll shead[MAXN]; // shead 用来临时保存 head 的副本
    ll level[MAXN]; // 节点所在层次
    // 链式前向星
    struct edge {
        ll to, next, flow; // 分别代表：边的终点、同起点的下一条边的编号、边的流量
        edge() {}
        edge(ll _to, ll _next, ll _flow): to(_to), next(_next), flow(_flow) {}
    }e[MAXM];       // 边数组 
    Dinic() {}
    // 初始化前向星结构
    void init(ll n) {
        cnt_edge = 0;
        memset(head, -1, sizeof(ll)*(n+1));
    }
    // 添加边（正反向两条边）
    void addEdge(ll u, ll v, ll w) {
        e[cnt_edge].to = v;
        e[cnt_edge].next = head[u];
        e[cnt_edge].flow = w;
        head[u] = cnt_edge++;
        e[cnt_edge].to = u;
        e[cnt_edge].next = head[v];
        e[cnt_edge].flow = 0;
        head[v] = cnt_edge++;
    }
    // BFS 寻找增广路，构建层次网络
    bool bfs(ll s, ll t, ll n) {
        memset(level, 0, sizeof(ll)*(n+1));
        queue <ll> bfsq;
        bfsq.push(s);
        level[s] = 1;   // 0 用来表示没有 bfs 到，故源点深度从 1 开始
        while(!bfsq.empty()) {
            ll u = bfsq.front();
            bfsq.pop();
            for(ll i = head[u]; i != -1; i = e[i].next) {
                ll v = e[i].to, w = e[i].flow;
                if(!level[v] && w) {
                    level[v] = level[u] + 1;
                    bfsq.push(v);
                }
            }
        }
        if(level[t])    return true;
        return false;
    }
    // DFS 进行路径增广
    ll dfs(ll u, ll curflow, ll t) {
        if(u == t) {
            return curflow;
        }
        for(ll & i = shead[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] == level[u] + 1 && w) {
                ll maxflow = dfs(v, min(curflow, w), t);
                if(maxflow) {
                    e[i].flow -= maxflow;
                    e[i^1].flow += maxflow;
                    return maxflow;
                }
            }
        }
        return 0;
    }
    // 求最大流
    ll maxFlow(ll s, ll t, ll n) {
        ll ans = 0;
        while(bfs(s,t,n)) {
            ll maxflow = INF, curflow;
            memcpy(shead, head, sizeof(head));
            while((curflow = dfs(s, maxflow, t))) {
                ans += curflow;
            }
        }
        return ans;
    }
};

unordered_map < string, int > ump;

int main()
{
    Dinic dinic;
    char s[4], t[4];
    int n = 1, m = 0;
    scanf("%s%s%d", s, t, &m);
    ump[s] = n++;
    ump[t] = n++;
    
    dinic.init(MAXN-1);
    for(int i = m; i; --i) {
        char ts[4], tv[4];
        int tst, tvt, cap;
        scanf("%s%s%d", ts, tv, &cap);
        if(ump.count(ts) == 0) {
            ump[ts] = n++;
        }
        if(ump.count(tv) == 0) {
            ump[tv] = n++;
        }
        tst = ump[ts];
        tvt = ump[tv];
        dinic.addEdge(tst, tvt, cap);
    }
    printf("%d\n", dinic.maxFlow(ump[s],ump[t],n));
    return 0;
}

  • ISAP 算法

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <bits/stdc++.h>
using namespace std;

// ISAP 算法
struct ISAP {
    #ifndef _ISAP_
    #define ll long long 
    #define MAXN 1205
    #define MAXM 1205
    #define INF 1e12
    #endif
    
    ll cnt_edge;    // 边数
    ll head[MAXN];  // 节点的第一条边的编号
    ll shead[MAXN]; // shead 用来临时保存 head 的副本
    ll level[MAXN]; // 节点所在层次
    ll gap[MAXN+1];   // 层次节点数
    // 链式前向星
    struct edge {
        ll to, next, flow; // 分别代表：边的终点、同起点的下一条边的编号、边的流量
        edge() {}
        edge(ll _to, ll _next, ll _flow): to(_to), next(_next), flow(_flow) {}
    }e[MAXM];       // 边数组 
    ISAP() {}
    // 初始化前向星结构
    void init(ll n) {
        cnt_edge = 0;
        memset(head, -1, sizeof(ll)*(n+1));
    }
    // 添加边（正反向两条边）
    void addEdge(ll u, ll v, ll w) {
        e[cnt_edge].to = v;
        e[cnt_edge].next = head[u];
        e[cnt_edge].flow = w;
        head[u] = cnt_edge++;
        e[cnt_edge].to = u;
        e[cnt_edge].next = head[v];
        e[cnt_edge].flow = 0;
        head[v] = cnt_edge++;
    }
    // BFS 寻找增广路，构建层次网络
    bool bfs(ll s, ll t, ll n) {
        memset(level, 0, sizeof(ll)*(n+1));
        memset(gap, 0, sizeof(ll)*(n+2));   // 最大 level 可达 n+1（见下文）
        queue <ll> bfsq;
        level[t] = 1;   // 0 用来表示没有 bfs 到，故到汇点的距离从 1 开始
        gap[1] = 1;    
        bfsq.push(t); 
        while(!bfsq.empty()) {
            ll u = bfsq.front();
            bfsq.pop();
            for(ll i = head[u]; i != -1; i = e[i].next) {
                // 在反图中构建层次网络，故需反向判断路径容量
                ll v = e[i].to;
                if(!level[v] && e[i^1].flow) {
                    level[v] = level[u] + 1;
                    ++gap[level[v]];
                    bfsq.push(v);
                }
            }
        }
        // 判断 s 到 t 是否有增广路
        if(level[s])    return true;
        return false;
    }
    // 重贴标签（更新层次深度）
    void relabel(ll u, ll n) {
        level[u] = n + 1;
        for(ll i = head[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] < level[u] - 1 && w) {
                level[u] = level[v] + 1;
            }
        }
    }
    // DFS 进行路径增广
    ll dfs(ll u, ll curflow, ll s, ll t, ll n) {
        if(u == t) {
            return curflow;
        }
        for(ll & i = shead[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] == level[u] - 1 && w) {
                ll maxflow = dfs(v, min(curflow, w), s, t, n);
                if(maxflow) {
                    e[i].flow -= maxflow;
                    e[i^1].flow += maxflow;
                    return maxflow;
                }
            }
        }
        // 程序执行到此说明该点出去的所有点都已经流过了
        // 此时需要更改层次深度
        // 同样要更新对应点的 shead
        shead[u] = head[u];
        --gap[level[u]];
        if(gap[level[u]] == 0) {
            level[s] = n + 1;
        }
        // 提高当前层次深度（因为可能存在路径更长的增广）
        // 方案一：直接更新为出边的最小层次深度+1
        relabel(u, n);
        // 方案二：直接更新为原层次深度+1
        // ++level[u];
        ++gap[level[u]];
        return 0;
    }
    // 求最大流
    ll maxFlow(ll s, ll t, ll n) {
        ll ans = 0;
        if(bfs(s,t,n)) {
            ll maxflow = INF;
            memcpy(shead, head, sizeof(head));
            while(level[s] <= n) {
                ans += dfs(s, maxflow, s, t, n);
            }
        }
        return ans;
    }
};

unordered_map < string, int > ump;

int main()
{
    ISAP isap;
    char s[4], t[4];
    int n = 1, m = 0;
    scanf("%s%s%d", s, t, &m);
    ump[s] = n++;
    ump[t] = n++;
    
    isap.init(MAXN-1);
    for(int i = m; i; --i) {
        char ts[4], tv[4];
        int tst, tvt, cap;
        scanf("%s%s%d", ts, tv, &cap);
        if(ump.count(ts) == 0) {
            ump[ts] = n++;
        }
        if(ump.count(tv) == 0) {
            ump[tv] = n++;
        }
        tst = ump[ts];
        tvt = ump[tv];
        isap.addEdge(tst, tvt, cap);
    }
    printf("%d\n", isap.maxFlow(ump[s],ump[t],n));
    return 0;
}

  • HLPP 算法

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
#include <bits/stdc++.h>
using namespace std;

// HLPP 算法
struct HLPP {
    #ifndef _HLPP_
    #define ll long long 
    #define MAXN 1205
    #define MAXM 1205
    #define INF 1e12
    #endif
    
    ll cnt_edge;    // 边数
    ll head[MAXN];  // 节点的第一条边的编号
    ll rflow[MAXN]; // 每个点对应的余流（所有节点的余流初始化为0）
    ll level[MAXN]; // 节点所在层次
    ll flag[MAXN];  // 标记是否已经在层次深度链表数组中
    ll gap[MAXN<<1];        // 层次节点数，重贴标签后层次深度可能达到 2n
    // 层次深度结构体
    struct depth {
        ll node;    // 节点编号
        ll level;   // 节点层次深度
        depth() {}
        depth(ll _node, ll _level): node(_node), level(_level) {}
        bool operator < (const depth d) const {
            return level < d.level;
        }
    };
    // 层次深度优先队列
    priority_queue <depth> pq;
    // 链式前向星
    struct edge {
        ll to, next, flow; // 分别代表：边的终点、同起点的下一条边的编号、边的流量
        edge() {}
        edge(ll _to, ll _next, ll _flow): to(_to), next(_next), flow(_flow) {}
    }e[MAXM];       // 边数组 
    HLPP() {}
    // 初始化前向星结构
    void init(ll n) {
        cnt_edge = 0;
        memset(head, -1, sizeof(ll)*(n+1));
    }
    // 添加边（正反向两条边）
    void addEdge(ll u, ll v, ll w) {
        e[cnt_edge].to = v;
        e[cnt_edge].next = head[u];
        e[cnt_edge].flow = w;
        head[u] = cnt_edge++;
        e[cnt_edge].to = u;
        e[cnt_edge].next = head[v];
        e[cnt_edge].flow = 0;
        head[v] = cnt_edge++;
    }
    // BFS 寻找增广路，构建层次网络（反向构建）
    bool bfs(ll s, ll t, ll n) {
        memset(level, 0, sizeof(ll)*(n+1));
        queue <ll> bfsq;
        level[t] = 1;   // 0 用来表示没有 bfs 到，故到汇点的距离从 1 开始
        bfsq.push(t); 
        while(!bfsq.empty()) {
            ll u = bfsq.front();
            bfsq.pop();
            for(ll i = head[u]; i != -1; i = e[i].next) {
                // 在反图中构建层次网络，故需反向判断路径容量
                ll v = e[i].to;
                if(!level[v] && e[i^1].flow) {
                    level[v] = level[u] + 1;
                    bfsq.push(v);
                }
            }
        }
        // 判断 s 到 t 是否有增广路
        if(level[s])    return true;
        return false;
    }
    // 预流推进
    void preflowPush(ll u, ll s, ll t) {
        for(ll i = head[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] == level[u] - 1 && w) {
                ll maxflow = min(rflow[u], e[i].flow);
                e[i].flow -= maxflow;
                e[i^1].flow += maxflow;
                rflow[u] -= maxflow;
                rflow[v] += maxflow;
                if(v != s && v != t && !flag[v]) {
                    pq.push(depth{v, level[v]});
                    flag[v] = 1;
                }
                if(rflow[u] == 0) {
                    // 全部流量推送完毕
                    break;
                }
            }
        }
    }
    // 重贴标签（更新层次深度）
    void relabel(ll u, ll n) {
        level[u] = 2*n;
        for(ll i = head[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] < level[u] - 1 && w) {
                level[u] = level[v] + 1;
            }
        }
    }
    // 求最大流
    ll maxFlow(ll s, ll t, ll n) {
        if(!bfs(s,t,n)) {
            return 0;
        }
        // 防止s的临近节点过早的推流回s节点
        level[s] = n + 1;
        // 初始化 gap 数组
        memset(gap, 0, sizeof(ll)*((n+1)<<1));
        for(ll i = 1; i <= n; ++i) {
            if(level[i]) {
                ++gap[level[i]];
            }
        }
        // 设定源点 s 的出边节点初始余流
        for(ll i = head[s]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(w) {
                e[i].flow -= w;
                e[i^1].flow += w;
                rflow[s] -= w;
                rflow[v] += w;
                if(v != s && v != t && !flag[v]) {
                    pq.push(depth{v, level[v]});
                    flag[v] = 1;
                }
            }
        }
        // 开始从最高高度节点预推流
        while(!pq.empty()) {
            ll u = pq.top().node;
            pq.pop();
            flag[u] = 0;
            preflowPush(u, s, t);
            if(rflow[u]) {
                // 如果当前节点还有余流
                --gap[level[u]];
                if(!gap[level[u]]) {
                    // 断层
                    for(ll v = 1; v <= n; ++v) {
                        if(v != s && v != t && level[v] > level[u] && level[v] < n + 1) {
                            level[v] = n + 1;
                        }
                    }
                }
                relabel(u, n); // 重贴标签，提升高度
                ++gap[level[u]];
                pq.push(depth{u, level[u]});
                flag[u] = 1;
            }
        }
        return rflow[t];
    }
};

unordered_map < string, int > ump;

int main()
{
    HLPP hlpp;
    char s[4], t[4];
    int n = 1, m = 0;
    scanf("%s%s%d", s, t, &m);
    ump[s] = n++;
    ump[t] = n++;
    
    hlpp.init(MAXN-1);
    for(int i = m; i; --i) {
        char ts[4], tv[4];
        int tst, tvt, cap;
        scanf("%s%s%d", ts, tv, &cap);
        if(ump.count(ts) == 0) {
            ump[ts] = n++;
        }
        if(ump.count(tv) == 0) {
            ump[tv] = n++;
        }
        tst = ump[ts];
        tvt = ump[tv];
        hlpp.addEdge(tst, tvt, cap);
    }
    printf("%d\n", hlpp.maxFlow(ump[s],ump[t],n));
    return 0;
}
Technique ACM 题解
Technique ACM 题解

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！