Advertisement
VladNitu

makeSpanVladAccLin

Apr 25th, 2023
111
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 10.45 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. pair<int, int> min_cost_max_flow(int source, int sink) {
  160. int total_cost = 0;
  161. int total_flow = 0;
  162. vector<Edge *> p;
  163. while (find_path(source, sink, p)) {
  164. int flow = INT_MAX;
  165. for (int i = 0; i < p.size(); ++i)
  166. if (p[i]->c - p[i]->f < flow) flow = p[i]->c - p[i]->f;
  167.  
  168. int cost = 0;
  169. for (int i = 0; i < p.size(); ++i) {
  170. cost += p[i]->w;
  171. p[i]->f += flow;
  172. p[i]->r->f -= flow;
  173. }
  174. total_flow += flow;
  175. cost *= flow; //cost per flow
  176. total_cost += cost;
  177. }
  178. return {total_flow, total_cost};
  179. }
  180.  
  181. void add_edge(int a, int b, int c, int w) {
  182. Edge *e = new Edge(a, b, c, 0, w);
  183. Edge *re = new Edge(b, a, 0, 0, -w);
  184. e->r = re;
  185. re->r = e;
  186. adj[a].push_back(e);
  187. adj[b].push_back(re);
  188. }
  189.  
  190. int run(int source, int sink) {
  191. const auto [max_flow, min_cost] = min_cost_max_flow(source, sink);
  192. for (int i = 0; i < node_count; ++i) {
  193. for (unsigned int j = 0; j < adj[i].size(); ++j)
  194. delete adj[i][j];
  195. adj[i].clear();
  196. }
  197.  
  198. return max_flow;
  199. }
  200. };
  201.  
  202. void read() {
  203. cin >> N >> M >> K;
  204. G.resize(N + 1);
  205. for (int i = 0; i < M; ++i) {
  206. cin >> x >> y >> w;
  207. G[x].push_back({y, w});
  208. }
  209.  
  210. int pathLength;
  211. vector<pair<int, int>> path;
  212.  
  213. starts.resize(K);
  214. for (int i = 0; i < K; ++i) {
  215. cin >> starts[i];
  216. }
  217.  
  218. for (int x = 0; x < K; ++x) {
  219. cin >> pathLength;
  220. path.resize(pathLength);
  221.  
  222. for (int j = 0; j < pathLength; ++j) {
  223. cin >> y >> t;
  224. path[j] = {y, t};
  225.  
  226. }
  227.  
  228. paths.push_back(path);
  229. }
  230. }
  231.  
  232. int IDX = 0;
  233. vector<vector<int>> node_time; // nodes x TMAX
  234. vector<vector<int>> node_time_double;
  235. vector<int> targetIds;
  236.  
  237.  
  238.  
  239. MaxFlowMinCost *constructFlowGraph(int nodes, int max_edge) {
  240.  
  241. node_time = vector<vector<int>>(N, vector<int>(TMAX + 5, -1));
  242. node_time_double = vector<vector<int>>(N, vector<int>(TMAX + 5, -1));
  243. targetIds = vector<int>(K + 1, -1);
  244. vector<vector<bool> >viz = vector<vector<bool>>(N, vector<bool>(TMAX + 5, false));
  245.  
  246. IDX = -1;
  247.  
  248. source = ++IDX; // 0
  249. sink = ++IDX; // 1
  250.  
  251. // T1, T2, .., Tk -> nodes - k, nodes-k - 1, ..., nodes - k - (k + 1) = nodes - 1
  252.  
  253. MaxFlowMinCost *maxFlowMinCost = new MaxFlowMinCost(nodes);
  254.  
  255. queue<pair<int, int>> nodesInCurrT;
  256.  
  257. for (int agentId = 0; agentId < K; ++agentId) { // First layer s -> agents & double it
  258. int agentNode = starts[agentId];
  259. node_time[agentNode][0] = ++IDX;
  260. maxFlowMinCost->add_edge(source, node_time[agentNode][0], 1, 0);
  261.  
  262. nodesInCurrT.push({agentNode, 0});
  263. }
  264.  
  265. // dbg(nodesInCurrT.size()); // = K
  266.  
  267.  
  268. while (!nodesInCurrT.empty()) {
  269.  
  270. const auto [currNode, currTime] = nodesInCurrT.front();
  271. nodesInCurrT.pop();
  272.  
  273. if (currTime > max_edge || viz[currNode][currTime]) // skip
  274. continue;
  275.  
  276. viz[currNode][currTime] = true;
  277.  
  278. if (node_time_double[currNode][currTime] == -1)
  279. node_time_double[currNode][currTime] = ++IDX;
  280.  
  281. maxFlowMinCost->add_edge(node_time[currNode][currTime], node_time_double[currNode][currTime], 1, 0); // Double node
  282.  
  283.  
  284. int currNodeFromId = node_time_double[currNode][currTime] ; // Now start to create edges out the DUPLICATED NODE
  285.  
  286. // If agent waits in this node => add edge (node, i) -> (node, i + 1) w/ `w = 1 = (i + 1) - i`
  287. if (node_time[currNode][currTime + 1] == -1)
  288. node_time[currNode][currTime + 1] = ++IDX;
  289. maxFlowMinCost->add_edge(currNodeFromId, node_time[currNode][currTime + 1], 1, 1); // w = 1
  290.  
  291. nodesInCurrT.push({currNode, currTime + 1}); // Agent waits - Add to queue only nodes that ARE NOT DUPLICATED
  292.  
  293. for (const auto &[neigh, time]: G[currNode]) {
  294. if (time + currTime > max_edge)
  295. continue;
  296. if (node_time[neigh][time + currTime] == -1)
  297. node_time[neigh][time + currTime] = ++IDX;
  298.  
  299. maxFlowMinCost->add_edge(currNodeFromId, node_time[neigh][time + currTime], 1, time);
  300.  
  301. //dbg(currNode, neigh, time, time + currTime, currTime);
  302.  
  303. nodesInCurrT.push({neigh, time + currTime});
  304. }
  305. }
  306.  
  307. // dbg("step1 done");
  308.  
  309. // T0, T1, .., T_{k - 1} -> nodes - k + 0, nodes - k + 1, ..., nodes - k + (k - 1) = nodes - 1
  310. // T_i = nodes - k + i
  311. // Add nodes to Targets (last layer)
  312.  
  313. for (int targetId = 0; targetId < K; ++targetId) {
  314. for (const auto [targetNode, targetTime]: paths[targetId]) {
  315. //dbg(targetId, targetNode, targetTime);
  316. if (node_time_double[targetNode][targetTime] ==
  317. -1 || targetTime > max_edge) // skip, as this target cannot be caught at this specific time
  318. continue;
  319.  
  320. if (targetIds[targetId] == -1)
  321. targetIds[targetId] = ++IDX;
  322.  
  323. maxFlowMinCost->add_edge(node_time_double[targetNode][targetTime], targetIds[targetId], 1, 0);
  324. // dbg("yes", targetNode, targetTime);
  325. }
  326. int node = paths[targetId].back().first;
  327. for (int t = paths[targetId].back().second + 1; t <= max_edge; ++t) {
  328. if (node_time_double[node][t] ==
  329. -1) // skip, as this target cannot be caught at this specific time
  330. continue;
  331.  
  332. if (targetIds[targetId] == -1)
  333. targetIds[targetId] = ++IDX;
  334.  
  335. maxFlowMinCost->add_edge(node_time_double[node][t], targetIds[targetId], 1, 0);
  336. }
  337. }
  338.  
  339. for (int targetId = 0; targetId < K; ++targetId) {
  340. if (targetIds[targetId] != -1)
  341. maxFlowMinCost->add_edge(targetIds[targetId], sink, 1, 0);
  342. }
  343.  
  344.  
  345.  
  346. return maxFlowMinCost;
  347.  
  348. }
  349.  
  350. void solveMakeSpan() {
  351.  
  352. int makeSpan = INT_MAX;
  353.  
  354. for (int mid = 0; mid <= TMAX; ++mid) {
  355. auto *maxFlowMinCost = constructFlowGraph(2 * N * TMAX + K + 2, mid);
  356. int max_flow = maxFlowMinCost->run(source, sink);
  357. delete maxFlowMinCost;
  358.  
  359. if (max_flow == K) { // Can match -> CUPLAJ
  360. makeSpan = mid;
  361. break;
  362. }
  363. }
  364.  
  365. cout << makeSpan << '\n';
  366. }
  367.  
  368.  
  369.  
  370. int main() {
  371.  
  372. // freopen("./tests/mincost/xl-sparse-9.in", "r", stdin);
  373. // freopen("./tests/mincost/xl-sparse-9.out", "w", stdout);
  374.  
  375.  
  376. // NOTE: N <= 40; K <= 25
  377. read();
  378.  
  379. solveMakeSpan();
  380. return 0;
  381. }
  382.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement