Advertisement
Guest User

Untitled

a guest
May 27th, 2018
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1.  
  2. #include "vector"
  3. #include "iostream"
  4. using namespace std;
  5.  
  6. struct five {
  7. int minute, x0, y0, x1, y1;
  8. };
  9.  
  10. inline bool check(five f1, five f2) {
  11. int t1 = f1.minute +
  12. abs(f1.x0 - f1.x1) +
  13. abs(f1.y0 - f1.y1);
  14. int dt = abs(f1.x1 - f2.x0) +
  15. abs(f1.y1 - f2.y0);
  16. return t1 + dt < f2.minute;
  17. }
  18.  
  19. vector<vector<int>> g;
  20. vector<int> pairs;
  21. vector<char> used;
  22. int cnt = 0;
  23. bool dfs_kuhn(int v) {
  24. if (used[v])
  25. return false;
  26. used[v] = true;
  27. for (int to : g[v]) {
  28. if(pairs[to] == -1)
  29. cnt++;
  30. if (pairs[to] == -1 || dfs_kuhn(pairs[to])) {
  31. pairs[to] = v;
  32. return true;
  33. }
  34. }
  35. return false;
  36. }
  37.  
  38. int main() {
  39. ios_base::sync_with_stdio(false);
  40. cin.tie(NULL);
  41. cout.tie(NULL);
  42. int M;
  43.  
  44. vector<five> ords;
  45.  
  46. cin >> M;
  47. g.resize(M);
  48.  
  49. for (int i = 0; i < M; ++i) {
  50. int h, m, x0, y0, x1, y1;
  51. char c;
  52. cin >> h >> c >> m >> x0 >> y0 >> x1 >> y1;
  53. five f = {h * 60 + m, x0, y0, x1, y1};
  54. for (int i = 0; i < ords.size(); ++i) {
  55. if (check(ords[i], f)){
  56. g[i].push_back(ords.size());
  57. }
  58. }
  59. ords.push_back(f);
  60. }
  61.  
  62. pairs.assign(M, -1);
  63. for(int v = 0; v < M; ++v) {
  64. used.assign(M, false);
  65. dfs_kuhn(v);
  66. }
  67.  
  68. cout << M - cnt << '\n';
  69.  
  70. return 0;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement