Advertisement
VladNitu

dianaMinCostAcc

Apr 24th, 2023
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 9.08 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <climits>
  5. #include <algorithm>
  6. #include <fstream>
  7.  
  8. #define MAXN 100000// maximum number of nodes in graph
  9. #define NMAX 100 + 5
  10. #define TMAX 1000 + 5
  11. using namespace std;
  12.  
  13. void __print(int x) { cerr << x; }
  14.  
  15. void __print(long x) { cerr << x; }
  16.  
  17. void __print(long long x) { cerr << x; }
  18.  
  19. void __print(unsigned x) { cerr << x; }
  20.  
  21. void __print(unsigned long x) { cerr << x; }
  22.  
  23. void __print(unsigned long long x) { cerr << x; }
  24.  
  25. void __print(float x) { cerr << x; }
  26.  
  27. void __print(double x) { cerr << x; }
  28.  
  29. void __print(long double x) { cerr << x; }
  30.  
  31. void __print(char x) { cerr << '\'' << x << '\''; }
  32.  
  33. void __print(const char *x) { cerr << '\"' << x << '\"'; }
  34.  
  35. void __print(const string &x) { cerr << '\"' << x << '\"'; }
  36.  
  37. void __print(bool x) { cerr << (x ? "true" : "false"); }
  38.  
  39. template<typename T, typename V, typename W>
  40. void __print(const std::tuple<T, V, W> &x) {
  41. cerr << '{';
  42. __print(std::get<0>(x));
  43. cerr << ',';
  44. __print(std::get<1>(x));
  45. cerr << ',';
  46. __print(std::get<2>(x));
  47. cerr << '}';
  48. }
  49.  
  50. template<typename T, typename V>
  51. void __print(const pair<T, V> &x) {
  52. cerr << '{';
  53. __print(x.first);
  54. cerr << ',';
  55. __print(x.second);
  56. cerr << '}';
  57. }
  58.  
  59. template<typename T>
  60. void __print(const T &x) {
  61. int f = 0;
  62. cerr << '{';
  63. for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
  64. cerr << "}";
  65. }
  66.  
  67. void _print() { cerr << "]\n"; }
  68.  
  69. template<typename T, typename... V>
  70. void _print(T t, V... v) {
  71. __print(t);
  72. if (sizeof...(v)) cerr << ", ";
  73. _print(v...);
  74. }
  75.  
  76. #ifndef ONLINE_JUDGE
  77. #define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
  78. #else
  79. #define dbg(x...)
  80. #endif
  81.  
  82.  
  83.  
  84. int n, m, k;
  85. int start, destination, weight;
  86. int startOfNewAgent;
  87. int vertex, steps, timeStamp;
  88.  
  89.  
  90. std::vector<int> agents;
  91. std::vector<std::vector<std::pair<int, int>>> targetPath;
  92.  
  93. // edges in the original graph
  94. int edges[NMAX][NMAX];
  95.  
  96. int viz[NMAX][TMAX];
  97.  
  98.  
  99. struct Edge
  100. {
  101. Edge(int _a, int _b, int _c, int _f, int _w) {
  102. a = _a; b = _b; c = _c; f = _f; w = _w;
  103. }
  104. ~Edge() { };
  105. int a; //from
  106. int b; //to
  107. int c; //capacity
  108. int f; //flow
  109. int w; //weight
  110. Edge* r;
  111. };
  112.  
  113.  
  114. const int MAX_DIST = 2000000; //do not choose INT_MAX because you are adding weights to it
  115. std::vector<Edge*> adj[MAXN];
  116. int distances[MAXN];
  117. Edge* parents[MAXN];
  118.  
  119. int nodecount;
  120. int source;
  121. int sink;
  122.  
  123. std::vector<std::vector<int>> layer_on_timestamp;
  124. std::vector<std::vector<int>> layer_on_double_timestamp;
  125. std::vector<int> sinks;
  126.  
  127. std::vector<int> possibleMakeSpan;
  128.  
  129. // bellman - ford
  130. bool find_path(int from, int to, std::vector<Edge*>& output)
  131. {
  132. std::fill(distances, distances+nodecount, MAX_DIST);
  133. std::fill(parents, parents+nodecount, (Edge*)0);
  134. distances[from] = 0;
  135.  
  136. bool updated = true;
  137. while(updated)
  138. {
  139. updated = false;
  140. for(int j = 0; j < nodecount; ++j)
  141. for(int k = 0; k < (int)adj[j].size(); ++k){
  142. Edge* e = adj[j][k];
  143. if( e->f >= e->c ) continue;
  144. if( distances[e->b] > distances[e->a] + e->w )
  145. {
  146. //std::cerr << distances[e->b] << " " << distances[e->a] << " " << e->w << std::endl;
  147. distances[e->b] = distances[e->a] + e->w;
  148. parents[e->b] = e;
  149. updated = true;
  150. }
  151. }
  152. }
  153. output.clear();
  154. if(distances[to] == MAX_DIST) return false;
  155. int cur = to;
  156. while(parents[cur])
  157. {
  158. output.push_back(parents[cur]);
  159. cur = parents[cur]->a;
  160. }
  161. return true;
  162. }
  163.  
  164. // MAX FLOW MIN COST IMPLEMENTATION
  165. int min_cost_max_flow(int source, int sink)
  166. {
  167. int total_cost = 0;
  168.  
  169. int totalFlow = 0;
  170. std::vector<Edge*> p;
  171. while(find_path(source, sink, p))
  172. {
  173. int flow = INT_MAX;
  174. for(int i = 0; i < p.size(); ++i)
  175. if(p[i]->c - p[i]->f < flow) flow = p[i]->c - p[i]->f;
  176.  
  177. int cost = 0;
  178. for(int i = 0; i < p.size(); ++i) {
  179. cost += p[i]->w;
  180. p[i]->f += flow;
  181. p[i]->r->f -= flow;
  182. }
  183. cost *= flow; //cost per flow
  184. total_cost += cost;
  185. totalFlow += flow;
  186. }
  187.  
  188. return total_cost;
  189. }
  190.  
  191. void add_edge(int a, int b, int c, int w)
  192. {
  193. Edge* e = new Edge(a, b, c, 0, w);
  194. Edge* re = new Edge(b, a, 0, 0, -w);
  195. e->r = re;
  196. re->r = e;
  197. adj[a].push_back(e);
  198. adj[b].push_back(re);
  199. }
  200.  
  201.  
  202. int main() {
  203. //std::ifstream cin("date.in");
  204. // freopen("date.in" , "r", stdin);
  205.  
  206. // read vertex num, edges num and k (agent/target count)
  207. std::cin >> n >> m >> k;
  208.  
  209. // read graph
  210. for(int i = 0; i < m; i++) {
  211. std::cin >> start >> destination >> weight;
  212.  
  213. // directed graph add just one time
  214. edges[start][destination] = weight;
  215. }
  216.  
  217. // see where the agents are starting -> value of index for each
  218. for(int i = 0; i < k; i++) {
  219. std::cin >> startOfNewAgent;
  220. agents.push_back(startOfNewAgent);
  221. }
  222.  
  223. // see the steps that each target makes -> (vertex, time)
  224. for(int i = 0; i < k; i++) {
  225. std::cin >> steps;
  226.  
  227. std::vector<std::pair<int, int>> path;
  228. for (int j = 0; j < steps; j++) {
  229. std::cin >> vertex >> timeStamp;
  230. path.push_back(std::make_pair(vertex, timeStamp));
  231.  
  232. }
  233.  
  234. targetPath.push_back(path);
  235. }
  236.  
  237. // construct graph
  238. source = 0;
  239. sink = 1;
  240.  
  241. int id = 2;
  242. int max_timestamp = 1000;
  243.  
  244. layer_on_timestamp.resize(TMAX + 1, vector<int>(NMAX + 1, -1));
  245. layer_on_double_timestamp.resize(TMAX + 1, vector<int>(NMAX + 1, -1));
  246.  
  247.  
  248. // create the sink and the corresponding edges
  249. for(int target = 0; target < k; target ++) {
  250. sinks.push_back(id);
  251. // add edges to the sink from the target
  252. add_edge(sinks[target], sink, 1, 0);
  253. id++;
  254. }
  255.  
  256. // construct rest of the matrix
  257. std::queue<std::pair<int, int>> queue; // node, timestamp pair
  258.  
  259. // go through all the agents and create edges from the source
  260. for(int i = 0; i < k ; i++) {
  261. queue.push(std::make_pair(agents[i], 0));
  262. layer_on_timestamp[0][agents[i]] = id ++;
  263. add_edge(source, layer_on_timestamp[0][agents[i]], 1, 0);
  264. }
  265.  
  266. while(!queue.empty()) {
  267. std::pair<int, int> current = queue.front();
  268. queue.pop();
  269.  
  270. int node = current.first;
  271. int timestamp = current.second;
  272.  
  273. if (timestamp > max_timestamp || viz[node][timestamp])
  274. continue;
  275.  
  276. viz[node][timestamp] = 1;
  277.  
  278. if (layer_on_double_timestamp[timestamp][node] == -1)
  279. layer_on_double_timestamp[timestamp][node] = id ++;
  280.  
  281.  
  282. // stay in place
  283. if(timestamp + 1 < max_timestamp) {
  284. if(layer_on_timestamp[timestamp + 1][node] == -1)
  285. layer_on_timestamp[timestamp + 1][node] = id ++;
  286.  
  287. add_edge(layer_on_double_timestamp[timestamp][node], layer_on_timestamp[timestamp + 1][node], 1,
  288. 1);
  289. queue.push(std::make_pair(node, timestamp + 1));
  290. }
  291.  
  292. for (int i = 0; i < n; i++) {
  293. int forward = edges[node][i];
  294.  
  295. if (timestamp + forward < max_timestamp && forward != 0) {
  296. if (layer_on_timestamp[timestamp + forward][i] == -1)
  297. layer_on_timestamp[timestamp + forward][i] = id ++;
  298.  
  299. add_edge(layer_on_double_timestamp[timestamp][node], layer_on_timestamp[timestamp + forward][i], 1,
  300. forward);
  301. queue.push(std::make_pair(i, timestamp + forward));
  302. }
  303. }
  304.  
  305. }
  306.  
  307. // create edges from targets to the sink target
  308. for(int target = 0; target < k; target ++) {
  309. int sink_of_target = sinks[target];
  310.  
  311. std::vector<std::pair<int, int>> path = targetPath[target];
  312.  
  313. // position -> vertex, timestamp
  314. for (auto position: path) {
  315. if (layer_on_double_timestamp[position.second][position.first] == -1)
  316. layer_on_double_timestamp[position.second][position.first] = id ++;
  317.  
  318. add_edge(layer_on_double_timestamp[position.second][position.first], sink_of_target, 1, 0);
  319. }
  320.  
  321. std::pair<int, int> last_node = path.back();
  322. for(int i = last_node.second + 1; i < max_timestamp; i++) {
  323. if (layer_on_double_timestamp[i][last_node.first] == -1)
  324. layer_on_double_timestamp[i][last_node.first] = id ++;
  325.  
  326. add_edge(layer_on_double_timestamp[i][last_node.first], sink_of_target, 1, 0);
  327. }
  328. }
  329.  
  330. for (int t = 0; t < max_timestamp; ++t)
  331. for (int i = 0; i < n; ++i)
  332. if (layer_on_timestamp[t][i] || layer_on_double_timestamp[t][i]) {
  333. add_edge(layer_on_timestamp[t][i], layer_on_double_timestamp[t][i], 1, 0);
  334. }
  335.  
  336.  
  337. nodecount = id + 5;
  338. std::cout << min_cost_max_flow(source, sink) << std::endl;
  339. }
  340.  
  341.  
  342.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement