Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define TMAX (int)(1000)
- #define NMAX (int)(100)
- #define INF (int)(1e9)
- #define smallINF (int)(1e6) // avoid overflow: 25 * 25 * 1e6 <= INT_MAX
- #define ll long long
- #define mkp make_pair
- #define mkt make_tuple
- #define lsb(x) (x & -x)
- #define fo(i, n) for(int i=0,_n=(n);i<_n;i++)
- void __print(int x) { cerr << x; }
- void __print(long x) { cerr << x; }
- void __print(long long x) { cerr << x; }
- void __print(unsigned x) { cerr << x; }
- void __print(unsigned long x) { cerr << x; }
- void __print(unsigned long long x) { cerr << x; }
- void __print(float x) { cerr << x; }
- void __print(double x) { cerr << x; }
- void __print(long double x) { cerr << x; }
- void __print(char x) { cerr << '\'' << x << '\''; }
- void __print(const char *x) { cerr << '\"' << x << '\"'; }
- void __print(const string &x) { cerr << '\"' << x << '\"'; }
- void __print(bool x) { cerr << (x ? "true" : "false"); }
- template<typename T, typename V, typename W>
- void __print(const std::tuple<T, V, W> &x) {
- cerr << '{';
- __print(std::get<0>(x));
- cerr << ',';
- __print(std::get<1>(x));
- cerr << ',';
- __print(std::get<2>(x));
- cerr << '}';
- }
- template<typename T, typename V>
- void __print(const pair<T, V> &x) {
- cerr << '{';
- __print(x.first);
- cerr << ',';
- __print(x.second);
- cerr << '}';
- }
- template<typename T>
- void __print(const T &x) {
- int f = 0;
- cerr << '{';
- for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
- cerr << "}";
- }
- void _print() { cerr << "]\n"; }
- template<typename T, typename... V>
- void _print(T t, V... v) {
- __print(t);
- if (sizeof...(v)) cerr << ", ";
- _print(v...);
- }
- #ifndef ONLINE_JUDGE
- #define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
- #else
- #define dbg(x...)
- #endif
- int N, M, K, x, y, w, t;
- int source, sink;
- vector<vector<pair<int, int>>> G; // Directed graph, {neigh, time}
- vector<int> starts; // stores the starting node of each Agent
- vector<vector<pair<int, int>>> paths; // stores path of each Target
- class Edge {
- public:
- Edge(int _a, int _b, int _c, int _f, int _w) {
- a = _a;
- b = _b;
- c = _c;
- f = _f;
- w = _w;
- }
- ~Edge() {};
- int a; //from
- int b; //to
- int c; //capacity
- int f; //flow
- int w; //weight
- Edge *r;
- };
- class MaxFlowMinCost {
- public:
- static const int MAX_NODES = 100000;
- const int MAX_DIST = 2000000; //do not choose INT_MAX because you are adding weights to it
- vector<vector<Edge *>> adj;
- int distances[MAX_NODES];
- Edge *parents[MAX_NODES];
- int node_count;
- MaxFlowMinCost(int _nodes) {
- this->adj.resize(this->MAX_NODES);
- this->node_count = _nodes;
- }
- bool find_path(int from, int to, vector<Edge *> &output) // Assume no negative paths
- {
- fill(distances, distances + node_count, MAX_DIST);
- fill(parents, parents + node_count, (Edge *) 0);
- distances[from] = 0;
- bool updated = true;
- while (updated) {
- updated = false;
- for (int j = 0; j < node_count; ++j)
- for (int k = 0; k < (int) adj[j].size(); ++k) {
- Edge *e = adj[j][k];
- if (e->f >= e->c) continue;
- if (distances[e->b] > distances[e->a] + e->w) {
- distances[e->b] = distances[e->a] + e->w;
- parents[e->b] = e;
- updated = true;
- }
- }
- }
- output.clear();
- if (distances[to] == MAX_DIST) return false;
- int cur = to;
- while (parents[cur]) {
- output.push_back(parents[cur]);
- cur = parents[cur]->a;
- }
- return true;
- }
- pair<int, int> min_cost_max_flow(int source, int sink) {
- int total_cost = 0;
- int total_flow = 0;
- vector<Edge *> p;
- while (find_path(source, sink, p)) {
- int flow = INT_MAX;
- for (int i = 0; i < p.size(); ++i)
- if (p[i]->c - p[i]->f < flow) flow = p[i]->c - p[i]->f;
- int cost = 0;
- for (int i = 0; i < p.size(); ++i) {
- cost += p[i]->w;
- p[i]->f += flow;
- p[i]->r->f -= flow;
- }
- total_flow += flow;
- cost *= flow; //cost per flow
- total_cost += cost;
- }
- return {total_flow, total_cost};
- }
- void add_edge(int a, int b, int c, int w) {
- Edge *e = new Edge(a, b, c, 0, w);
- Edge *re = new Edge(b, a, 0, 0, -w);
- e->r = re;
- re->r = e;
- adj[a].push_back(e);
- adj[b].push_back(re);
- }
- int run(int source, int sink) {
- const auto [max_flow, min_cost] = min_cost_max_flow(source, sink);
- for (int i = 0; i < node_count; ++i) {
- for (unsigned int j = 0; j < adj[i].size(); ++j)
- delete adj[i][j];
- adj[i].clear();
- }
- return max_flow;
- }
- };
- void read() {
- cin >> N >> M >> K;
- G.resize(N + 1);
- for (int i = 0; i < M; ++i) {
- cin >> x >> y >> w;
- G[x].push_back({y, w});
- }
- int pathLength;
- vector<pair<int, int>> path;
- starts.resize(K);
- for (int i = 0; i < K; ++i) {
- cin >> starts[i];
- }
- for (int x = 0; x < K; ++x) {
- cin >> pathLength;
- path.resize(pathLength);
- for (int j = 0; j < pathLength; ++j) {
- cin >> y >> t;
- path[j] = {y, t};
- }
- paths.push_back(path);
- }
- }
- int IDX = 0;
- vector<vector<int>> node_time; // nodes x TMAX
- vector<vector<int>> node_time_double;
- vector<int> targetIds;
- MaxFlowMinCost *constructFlowGraph(int nodes, int max_edge) {
- node_time = vector<vector<int>>(N, vector<int>(TMAX + 5, -1));
- node_time_double = vector<vector<int>>(N, vector<int>(TMAX + 5, -1));
- targetIds = vector<int>(K + 1, -1);
- vector<vector<bool> >viz = vector<vector<bool>>(N, vector<bool>(TMAX + 5, false));
- IDX = -1;
- source = ++IDX; // 0
- sink = ++IDX; // 1
- // T1, T2, .., Tk -> nodes - k, nodes-k - 1, ..., nodes - k - (k + 1) = nodes - 1
- MaxFlowMinCost *maxFlowMinCost = new MaxFlowMinCost(nodes);
- queue<pair<int, int>> nodesInCurrT;
- for (int agentId = 0; agentId < K; ++agentId) { // First layer s -> agents & double it
- int agentNode = starts[agentId];
- node_time[agentNode][0] = ++IDX;
- maxFlowMinCost->add_edge(source, node_time[agentNode][0], 1, 0);
- nodesInCurrT.push({agentNode, 0});
- }
- // dbg(nodesInCurrT.size()); // = K
- while (!nodesInCurrT.empty()) {
- const auto [currNode, currTime] = nodesInCurrT.front();
- nodesInCurrT.pop();
- if (currTime > max_edge || viz[currNode][currTime]) // skip
- continue;
- viz[currNode][currTime] = true;
- if (node_time_double[currNode][currTime] == -1)
- node_time_double[currNode][currTime] = ++IDX;
- maxFlowMinCost->add_edge(node_time[currNode][currTime], node_time_double[currNode][currTime], 1, 0); // Double node
- int currNodeFromId = node_time_double[currNode][currTime] ; // Now start to create edges out the DUPLICATED NODE
- // If agent waits in this node => add edge (node, i) -> (node, i + 1) w/ `w = 1 = (i + 1) - i`
- if (node_time[currNode][currTime + 1] == -1)
- node_time[currNode][currTime + 1] = ++IDX;
- maxFlowMinCost->add_edge(currNodeFromId, node_time[currNode][currTime + 1], 1, 1); // w = 1
- nodesInCurrT.push({currNode, currTime + 1}); // Agent waits - Add to queue only nodes that ARE NOT DUPLICATED
- for (const auto &[neigh, time]: G[currNode]) {
- if (time + currTime > max_edge)
- continue;
- if (node_time[neigh][time + currTime] == -1)
- node_time[neigh][time + currTime] = ++IDX;
- maxFlowMinCost->add_edge(currNodeFromId, node_time[neigh][time + currTime], 1, time);
- //dbg(currNode, neigh, time, time + currTime, currTime);
- nodesInCurrT.push({neigh, time + currTime});
- }
- }
- // dbg("step1 done");
- // T0, T1, .., T_{k - 1} -> nodes - k + 0, nodes - k + 1, ..., nodes - k + (k - 1) = nodes - 1
- // T_i = nodes - k + i
- // Add nodes to Targets (last layer)
- for (int targetId = 0; targetId < K; ++targetId) {
- for (const auto [targetNode, targetTime]: paths[targetId]) {
- //dbg(targetId, targetNode, targetTime);
- if (node_time_double[targetNode][targetTime] ==
- -1 || targetTime > max_edge) // skip, as this target cannot be caught at this specific time
- continue;
- if (targetIds[targetId] == -1)
- targetIds[targetId] = ++IDX;
- maxFlowMinCost->add_edge(node_time_double[targetNode][targetTime], targetIds[targetId], 1, 0);
- // dbg("yes", targetNode, targetTime);
- }
- int node = paths[targetId].back().first;
- for (int t = paths[targetId].back().second + 1; t <= max_edge; ++t) {
- if (node_time_double[node][t] ==
- -1) // skip, as this target cannot be caught at this specific time
- continue;
- if (targetIds[targetId] == -1)
- targetIds[targetId] = ++IDX;
- maxFlowMinCost->add_edge(node_time_double[node][t], targetIds[targetId], 1, 0);
- }
- }
- for (int targetId = 0; targetId < K; ++targetId) {
- if (targetIds[targetId] != -1)
- maxFlowMinCost->add_edge(targetIds[targetId], sink, 1, 0);
- }
- return maxFlowMinCost;
- }
- void solveMakeSpan() {
- int makeSpan = INT_MAX;
- for (int mid = 0; mid <= TMAX; ++mid) {
- auto *maxFlowMinCost = constructFlowGraph(2 * N * TMAX + K + 2, mid);
- int max_flow = maxFlowMinCost->run(source, sink);
- delete maxFlowMinCost;
- if (max_flow == K) { // Can match -> CUPLAJ
- makeSpan = mid;
- break;
- }
- }
- cout << makeSpan << '\n';
- }
- int main() {
- // freopen("./tests/mincost/xl-sparse-9.in", "r", stdin);
- // freopen("./tests/mincost/xl-sparse-9.out", "w", stdout);
- // NOTE: N <= 40; K <= 25
- read();
- solveMakeSpan();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement