Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <climits>
- #include <algorithm>
- #include <fstream>
- #define MAXN 100000// maximum number of nodes in graph
- #define NMAX 100 + 5
- #define TMAX 1000 + 5
- using namespace std;
- 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;
- int start, destination, weight;
- int startOfNewAgent;
- int vertex, steps, timeStamp;
- std::vector<int> agents;
- std::vector<std::vector<std::pair<int, int>>> targetPath;
- // edges in the original graph
- int edges[NMAX][NMAX];
- int viz[NMAX][TMAX];
- struct Edge
- {
- 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;
- };
- const int MAX_DIST = 2000000; //do not choose INT_MAX because you are adding weights to it
- std::vector<Edge*> adj[MAXN];
- int distances[MAXN];
- Edge* parents[MAXN];
- int nodecount;
- int source;
- int sink;
- std::vector<std::vector<int>> layer_on_timestamp;
- std::vector<std::vector<int>> layer_on_double_timestamp;
- std::vector<int> sinks;
- std::vector<int> possibleMakeSpan;
- // bellman - ford
- bool find_path(int from, int to, std::vector<Edge*>& output)
- {
- std::fill(distances, distances+nodecount, MAX_DIST);
- std::fill(parents, parents+nodecount, (Edge*)0);
- distances[from] = 0;
- bool updated = true;
- while(updated)
- {
- updated = false;
- for(int j = 0; j < nodecount; ++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 )
- {
- //std::cerr << distances[e->b] << " " << distances[e->a] << " " << e->w << std::endl;
- 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;
- }
- // MAX FLOW MIN COST IMPLEMENTATION
- int min_cost_max_flow(int source, int sink)
- {
- int total_cost = 0;
- int totalFlow = 0;
- std::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;
- }
- cost *= flow; //cost per flow
- total_cost += cost;
- totalFlow += flow;
- }
- return 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 main() {
- //std::ifstream cin("date.in");
- // freopen("date.in" , "r", stdin);
- // read vertex num, edges num and k (agent/target count)
- std::cin >> n >> m >> k;
- // read graph
- for(int i = 0; i < m; i++) {
- std::cin >> start >> destination >> weight;
- // directed graph add just one time
- edges[start][destination] = weight;
- }
- // see where the agents are starting -> value of index for each
- for(int i = 0; i < k; i++) {
- std::cin >> startOfNewAgent;
- agents.push_back(startOfNewAgent);
- }
- // see the steps that each target makes -> (vertex, time)
- for(int i = 0; i < k; i++) {
- std::cin >> steps;
- std::vector<std::pair<int, int>> path;
- for (int j = 0; j < steps; j++) {
- std::cin >> vertex >> timeStamp;
- path.push_back(std::make_pair(vertex, timeStamp));
- }
- targetPath.push_back(path);
- }
- // construct graph
- source = 0;
- sink = 1;
- int id = 2;
- int max_timestamp = 1000;
- layer_on_timestamp.resize(TMAX + 1, vector<int>(NMAX + 1, -1));
- layer_on_double_timestamp.resize(TMAX + 1, vector<int>(NMAX + 1, -1));
- // create the sink and the corresponding edges
- for(int target = 0; target < k; target ++) {
- sinks.push_back(id);
- // add edges to the sink from the target
- add_edge(sinks[target], sink, 1, 0);
- id++;
- }
- // construct rest of the matrix
- std::queue<std::pair<int, int>> queue; // node, timestamp pair
- // go through all the agents and create edges from the source
- for(int i = 0; i < k ; i++) {
- queue.push(std::make_pair(agents[i], 0));
- layer_on_timestamp[0][agents[i]] = id ++;
- add_edge(source, layer_on_timestamp[0][agents[i]], 1, 0);
- }
- while(!queue.empty()) {
- std::pair<int, int> current = queue.front();
- queue.pop();
- int node = current.first;
- int timestamp = current.second;
- if (timestamp > max_timestamp || viz[node][timestamp])
- continue;
- viz[node][timestamp] = 1;
- if (layer_on_double_timestamp[timestamp][node] == -1)
- layer_on_double_timestamp[timestamp][node] = id ++;
- // stay in place
- if(timestamp + 1 < max_timestamp) {
- if(layer_on_timestamp[timestamp + 1][node] == -1)
- layer_on_timestamp[timestamp + 1][node] = id ++;
- add_edge(layer_on_double_timestamp[timestamp][node], layer_on_timestamp[timestamp + 1][node], 1,
- 1);
- queue.push(std::make_pair(node, timestamp + 1));
- }
- for (int i = 0; i < n; i++) {
- int forward = edges[node][i];
- if (timestamp + forward < max_timestamp && forward != 0) {
- if (layer_on_timestamp[timestamp + forward][i] == -1)
- layer_on_timestamp[timestamp + forward][i] = id ++;
- add_edge(layer_on_double_timestamp[timestamp][node], layer_on_timestamp[timestamp + forward][i], 1,
- forward);
- queue.push(std::make_pair(i, timestamp + forward));
- }
- }
- }
- // create edges from targets to the sink target
- for(int target = 0; target < k; target ++) {
- int sink_of_target = sinks[target];
- std::vector<std::pair<int, int>> path = targetPath[target];
- // position -> vertex, timestamp
- for (auto position: path) {
- if (layer_on_double_timestamp[position.second][position.first] == -1)
- layer_on_double_timestamp[position.second][position.first] = id ++;
- add_edge(layer_on_double_timestamp[position.second][position.first], sink_of_target, 1, 0);
- }
- std::pair<int, int> last_node = path.back();
- for(int i = last_node.second + 1; i < max_timestamp; i++) {
- if (layer_on_double_timestamp[i][last_node.first] == -1)
- layer_on_double_timestamp[i][last_node.first] = id ++;
- add_edge(layer_on_double_timestamp[i][last_node.first], sink_of_target, 1, 0);
- }
- }
- for (int t = 0; t < max_timestamp; ++t)
- for (int i = 0; i < n; ++i)
- if (layer_on_timestamp[t][i] || layer_on_double_timestamp[t][i]) {
- add_edge(layer_on_timestamp[t][i], layer_on_double_timestamp[t][i], 1, 0);
- }
- nodecount = id + 5;
- std::cout << min_cost_max_flow(source, sink) << std::endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement