Advertisement
VladNitu

minCost Vlad 2

Apr 24th, 2023
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.33 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define TMAX (int)(1000)
  6. #define NMAX (int)(100)
  7. #define INF (int)(1e9)
  8. #define smallINF (int)(1e6) // avoid overflow: 25 * 25 * 1e6 <= INT_MAX
  9. #define ll long long
  10. #define mkp make_pair
  11. #define mkt make_tuple
  12. #define lsb(x) (x & -x)
  13. #define fo(i, n) for(int i=0,_n=(n);i<_n;i++)
  14.  
  15. void __print(int x) { cerr << x; }
  16.  
  17. void __print(long x) { cerr << x; }
  18.  
  19. void __print(long long x) { cerr << x; }
  20.  
  21. void __print(unsigned x) { cerr << x; }
  22.  
  23. void __print(unsigned long x) { cerr << x; }
  24.  
  25. void __print(unsigned long long x) { cerr << x; }
  26.  
  27. void __print(float x) { cerr << x; }
  28.  
  29. void __print(double x) { cerr << x; }
  30.  
  31. void __print(long double x) { cerr << x; }
  32.  
  33. void __print(char x) { cerr << '\'' << x << '\''; }
  34.  
  35. void __print(const char *x) { cerr << '\"' << x << '\"'; }
  36.  
  37. void __print(const string &x) { cerr << '\"' << x << '\"'; }
  38.  
  39. void __print(bool x) { cerr << (x ? "true" : "false"); }
  40.  
  41. template<typename T, typename V, typename W>
  42. void __print(const std::tuple<T, V, W> &x) {
  43. cerr << '{';
  44. __print(std::get<0>(x));
  45. cerr << ',';
  46. __print(std::get<1>(x));
  47. cerr << ',';
  48. __print(std::get<2>(x));
  49. cerr << '}';
  50. }
  51.  
  52. template<typename T, typename V>
  53. void __print(const pair<T, V> &x) {
  54. cerr << '{';
  55. __print(x.first);
  56. cerr << ',';
  57. __print(x.second);
  58. cerr << '}';
  59. }
  60.  
  61. template<typename T>
  62. void __print(const T &x) {
  63. int f = 0;
  64. cerr << '{';
  65. for (auto &i: x) cerr << (f++ ? "," : ""), __print(i);
  66. cerr << "}";
  67. }
  68.  
  69. void _print() { cerr << "]\n"; }
  70.  
  71. template<typename T, typename... V>
  72. void _print(T t, V... v) {
  73. __print(t);
  74. if (sizeof...(v)) cerr << ", ";
  75. _print(v...);
  76. }
  77.  
  78. #ifndef ONLINE_JUDGE
  79. #define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
  80. #else
  81. #define dbg(x...)
  82. #endif
  83.  
  84.  
  85.  
  86.  
  87. int N, M, K, x, y, w, t;
  88. int source, sink;
  89. vector<vector<pair<int, int>>> G; // Directed graph, {neigh, time}
  90. vector<int> starts; // stores the starting node of each Agent
  91. vector<vector<pair<int, int>>> paths; // stores path of each Target
  92.  
  93. class Edge {
  94. public:
  95. Edge(int _a, int _b, int _c, int _f, int _w) {
  96. a = _a;
  97. b = _b;
  98. c = _c;
  99. f = _f;
  100. w = _w;
  101. }
  102.  
  103. ~Edge() {};
  104. int a; //from
  105. int b; //to
  106. int c; //capacity
  107. int f; //flow
  108. int w; //weight
  109. Edge *r;
  110.  
  111. };
  112.  
  113. class MaxFlowMinCost {
  114. public:
  115.  
  116. static const int MAX_NODES = 100000;
  117. const int MAX_DIST = 2000000; //do not choose INT_MAX because you are adding weights to it
  118. vector<vector<Edge *>> adj;
  119. int distances[MAX_NODES];
  120. Edge *parents[MAX_NODES];
  121. int node_count;
  122.  
  123. MaxFlowMinCost(int _nodes) {
  124. this->adj.resize(this->MAX_NODES);
  125. this->node_count = _nodes;
  126. }
  127.  
  128.  
  129. bool find_path(int from, int to, vector<Edge *> &output) // Assume no negative paths
  130. {
  131. fill(distances, distances + node_count, MAX_DIST);
  132. fill(parents, parents + node_count, (Edge *) 0);
  133. distances[from] = 0;
  134.  
  135. bool updated = true;
  136. while (updated) {
  137. updated = false;
  138. for (int j = 0; j < node_count; ++j)
  139. for (int k = 0; k < (int) adj[j].size(); ++k) {
  140. Edge *e = adj[j][k];
  141. if (e->f >= e->c) continue;
  142. if (distances[e->b] > distances[e->a] + e->w) {
  143. distances[e->b] = distances[e->a] + e->w;
  144. parents[e->b] = e;
  145. updated = true;
  146. }
  147. }
  148. }
  149. output.clear();
  150. if (distances[to] == MAX_DIST) return false;
  151. int cur = to;
  152. while (parents[cur]) {
  153. output.push_back(parents[cur]);
  154. cur = parents[cur]->a;
  155. }
  156. return true;
  157. }
  158.  
  159. int min_cost_max_flow(int source, int sink) {
  160. int total_cost = 0;
  161. vector<Edge *> p;
  162. while (find_path(source, sink, p)) {
  163. int flow = INT_MAX;
  164. for (int i = 0; i < p.size(); ++i)
  165. if (p[i]->c - p[i]->f < flow) flow = p[i]->c - p[i]->f;
  166.  
  167. int cost = 0;
  168. for (int i = 0; i < p.size(); ++i) {
  169. cost += p[i]->w;
  170. p[i]->f += flow;
  171. p[i]->r->f -= flow;
  172. }
  173. cost *= flow; //cost per flow
  174. total_cost += cost;
  175. }
  176. return total_cost;
  177. }
  178.  
  179. void add_edge(int a, int b, int c, int w) {
  180. Edge *e = new Edge(a, b, c, 0, w);
  181. Edge *re = new Edge(b, a, 0, 0, -w);
  182. e->r = re;
  183. re->r = e;
  184. adj[a].push_back(e);
  185. adj[b].push_back(re);
  186. }
  187.  
  188. int run(int source, int sink) {
  189. int ans = min_cost_max_flow(source, sink);
  190. for (int i = 0; i < node_count; ++i) {
  191. for (unsigned int j = 0; j < adj[i].size(); ++j)
  192. delete adj[i][j];
  193. adj[i].clear();
  194. }
  195.  
  196. return ans;
  197. }
  198. };
  199.  
  200. void read() {
  201. cin >> N >> M >> K;
  202. G.resize(N + 1);
  203. for (int i = 0; i < M; ++i) {
  204. cin >> x >> y >> w;
  205. G[x].push_back({y, w});
  206. }
  207.  
  208. int pathLength;
  209. vector<pair<int, int>> path;
  210.  
  211. starts.resize(K);
  212. for (int i = 0; i < K; ++i) {
  213. cin >> starts[i];
  214. }
  215.  
  216. for (int x = 0; x < K; ++x) {
  217. cin >> pathLength;
  218. path.resize(pathLength);
  219.  
  220. for (int j = 0; j < pathLength; ++j) {
  221. cin >> y >> t;
  222. path[j] = {y, t};
  223.  
  224. }
  225.  
  226. paths.push_back(path);
  227. }
  228. }
  229.  
  230. int IDX = 0;
  231. vector<vector<int>> node_time; // nodes x TMAX
  232. vector<vector<int>> node_time_double;
  233. vector<int> targetIds;
  234.  
  235.  
  236.  
  237. MaxFlowMinCost *constructFlowGraph(int nodes) {
  238.  
  239. node_time = vector<vector<int>>(N, vector<int>(TMAX + 1, -1));
  240. node_time_double = vector<vector<int>>(N, vector<int>(TMAX + 1, -1));
  241. targetIds = vector<int>(K + 1, -1);
  242. vector<vector<bool> >viz = vector<vector<bool>>(N, vector<bool>(TMAX + 1, false));
  243.  
  244. IDX = -1;
  245.  
  246. source = ++IDX; // 0
  247. sink = ++IDX; // 1
  248.  
  249. // T1, T2, .., Tk -> nodes - k, nodes-k - 1, ..., nodes - k - (k + 1) = nodes - 1
  250.  
  251. MaxFlowMinCost *maxFlowMinCost = new MaxFlowMinCost(nodes);
  252.  
  253. queue<pair<int, int>> nodesInCurrT;
  254.  
  255. for (int agentId = 0; agentId < K; ++agentId) { // First layer s -> agents & double it
  256. int agentNode = starts[agentId];
  257. node_time[agentNode][0] = ++IDX;
  258. maxFlowMinCost->add_edge(source, node_time[agentNode][0], 1, 0);
  259.  
  260. nodesInCurrT.push({agentNode, 0});
  261. }
  262.  
  263. // dbg(nodesInCurrT.size()); // = K
  264.  
  265.  
  266. while (!nodesInCurrT.empty()) {
  267.  
  268. const auto [currNode, currTime] = nodesInCurrT.front();
  269. nodesInCurrT.pop();
  270.  
  271. if (currTime >= TMAX || viz[currNode][currTime]) // skip
  272. continue;
  273.  
  274. viz[currNode][currTime] = true;
  275.  
  276. if (node_time_double[currNode][currTime] == -1)
  277. node_time_double[currNode][currTime] = ++IDX;
  278.  
  279. maxFlowMinCost->add_edge(node_time[currNode][currTime], node_time_double[currNode][currTime], 1, 0); // Double node
  280.  
  281.  
  282. int currNodeFromId = node_time_double[currNode][currTime] ; // Now start to create edges out the DUPLICATED NODE
  283.  
  284. // If agent waits in this node => add edge (node, i) -> (node, i + 1) w/ `w = 1 = (i + 1) - i`
  285. if (node_time[currNode][currTime + 1] == -1)
  286. node_time[currNode][currTime + 1] = ++IDX;
  287. maxFlowMinCost->add_edge(currNodeFromId, node_time[currNode][currTime + 1], 1, 1); // w = 1
  288.  
  289. nodesInCurrT.push({currNode, currTime + 1}); // Agent waits - Add to queue only nodes that ARE NOT DUPLICATED
  290.  
  291. for (const auto &[neigh, time]: G[currNode]) {
  292. if (time + currTime >= TMAX)
  293. continue;
  294. if (node_time[neigh][time + currTime] == -1)
  295. node_time[neigh][time + currTime] = ++IDX;
  296.  
  297. maxFlowMinCost->add_edge(currNodeFromId, node_time[neigh][time + currTime], 1, time);
  298.  
  299. //dbg(currNode, neigh, time, time + currTime, currTime);
  300.  
  301. nodesInCurrT.push({neigh, time + currTime});
  302. }
  303. }
  304.  
  305. // dbg("step1 done");
  306.  
  307. // T0, T1, .., T_{k - 1} -> nodes - k + 0, nodes - k + 1, ..., nodes - k + (k - 1) = nodes - 1
  308. // T_i = nodes - k + i
  309. // Add nodes to Targets (last layer)
  310.  
  311. for (int targetId = 0; targetId < K; ++targetId) {
  312. for (const auto [targetNode, targetTime]: paths[targetId]) {
  313. //dbg(targetId, targetNode, targetTime);
  314. if (node_time_double[targetNode][targetTime] ==
  315. -1) // skip, as this target cannot be caught at this specific time
  316. continue;
  317.  
  318. if (targetIds[targetId] == -1)
  319. targetIds[targetId] = ++IDX;
  320.  
  321. maxFlowMinCost->add_edge(node_time_double[targetNode][targetTime], targetIds[targetId], 1, 0);
  322. // dbg("yes", targetNode, targetTime);
  323. }
  324.  
  325. // If the agent reaches the last node without being caught, remain in that node
  326. int node = paths[targetId].back().first;
  327. for (int t = paths[targetId].back().second + 1; t <= TMAX; ++t) {
  328. if (node_time_double[node][t] ==
  329. -1) // skip, as this target cannot be caught at this specific time
  330. {
  331. //dbg("no", targetNode, targetTime);
  332. continue;
  333. }
  334.  
  335. if (targetIds[targetId] == -1)
  336. targetIds[targetId] = ++IDX;
  337.  
  338. maxFlowMinCost->add_edge(node_time_double[node][t], targetIds[targetId], 1, 0);
  339. }
  340. }
  341.  
  342. for (int targetId = 0; targetId < K; ++targetId) {
  343. if (targetIds[targetId] != -1)
  344. maxFlowMinCost->add_edge(targetIds[targetId], sink, 1, 0);
  345. // dbg(targetId, sink);
  346. }
  347.  
  348. // dbg(source, sink); // (0, 1)
  349. // for (int x = 0; x < targetIds.size(); ++x) {
  350. // dbg(x, targetIds[x]);
  351. // }
  352.  
  353. return maxFlowMinCost;
  354.  
  355. }
  356.  
  357.  
  358. int main() {
  359.  
  360. // freopen("./tests/mincost/xl-sparse-9.in", "r", stdin);
  361. // freopen("./tests/mincost/xl-sparse-9.out", "w", stdout);
  362.  
  363.  
  364. // NOTE: N <= 40; K <= 25
  365. read();
  366.  
  367. MaxFlowMinCost *maxFlowMinCost = constructFlowGraph(2 * N * TMAX + K + 2);
  368.  
  369. int minCost = maxFlowMinCost->run(source, sink);
  370. cout << minCost << '\n';
  371.  
  372. return 0;
  373. }
  374.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement