1003 Universal Travel Sites
Statement
Metadata
- 作者: CHEN, Yue
- 单位: 浙江大学
- 代码长度限制: 16 KB
- 时间限制: 200 ms
- 内存限制: 64 MB
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 N (N 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] source[i] to destination[i]. Each name is a string of 3 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
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
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
template <class Type>
struct Dinic {
static const int M = 2e6 + 10;
static const int N = 1e5 + 10;
struct Edge {
int to, nxt;
Type flow;
Edge() {}
Edge(int to, int nxt, Type flow) : to(to), nxt(nxt), flow(flow) {}
} edge[M];
int S, T;
int head[N], tot;
int dep[N];
void init() {
memset(head, -1, sizeof head);
tot = 0;
}
void set(int S, int T) {
this->S = S;
this->T = T;
}
void addedge(int u, int v, Type w, Type rw = 0) {
edge[tot] = Edge(v, head[u], w);
head[u] = tot++;
edge[tot] = Edge(u, head[v], rw);
head[v] = tot++;
}
bool BFS() {
memset(dep, -1, sizeof dep);
queue<int> q;
q.push(S);
dep[S] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (edge[i].flow && dep[edge[i].to] == -1) {
dep[edge[i].to] = dep[u] + 1;
q.push(edge[i].to);
}
}
}
return dep[T] >= 0;
}
Type DFS(int u, Type f) {
if (u == T || f == 0)
return f;
Type w, used = 0;
for (int i = head[u]; ~i; i = edge[i].nxt) {
if (edge[i].flow && dep[edge[i].to] == dep[u] + 1) {
w = DFS(edge[i].to, min(f - used, edge[i].flow));
edge[i].flow -= w;
edge[i ^ 1].flow += w;
used += w;
if (used == f)
return f;
}
}
if (!used)
dep[u] = -1;
return used;
}
Type solve() {
Type ans = 0;
while (BFS()) {
ans += DFS(S, INF);
}
return ans;
}
};
Dinic<ll> dinic;
map<string, int> mp;
int cnt, n;
string S, T;
inline int getID(const string &s) {
if (mp.count(s))
return mp[s];
mp[s] = ++cnt;
return cnt;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cnt = 0;
cin >> S >> T >> n;
mp.clear();
dinic.init();
for (int i = 1; i <= n; ++i) {
string _S, _T;
int w;
cin >> _S >> _T >> w;
int u = getID(_S), v = getID(_T);
dinic.addedge(u, v, w);
}
dinic.set(getID(S), getID(T));
cout << dinic.solve() << endl;
return 0;
}