Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.24 KB | None | 0 0
  1. #include <cstdlib>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <vector>
  5.  
  6. int nbPersonnes, nbVelos, nbReq;
  7. std::vector<int> noeuds[2000][2];
  8.  
  9. int dfs(int noeud, int last)
  10. {
  11. int maxi = 0;
  12.  
  13. for(int i = 0; i < noeuds[noeud][!last].size(); i++)
  14. maxi = std::max(maxi, dfs(noeuds[noeud][!last][i], !last) + last);
  15.  
  16. return maxi;
  17. }
  18.  
  19. int main()
  20. {
  21. int nbConfig = 0;
  22. scanf("%d%d%d", &nbPersonnes, &nbVelos, &nbReq);
  23.  
  24. for(int i = 0; i < nbReq; i++)
  25. {
  26. int a, b, ut;
  27.  
  28. scanf("%d%d%d", &a, &b, &ut);
  29. b+=nbPersonnes;
  30.  
  31. noeuds[a][ut].push_back(b);
  32. noeuds[b][ut].push_back(a);
  33.  
  34. nbConfig += ut;
  35. }
  36.  
  37. for(int i = 0; i < nbPersonnes+nbVelos; i++)
  38. {
  39. if(noeuds[i][1].empty())
  40. {
  41. char ok = 0;
  42. for(int j = 0; j < noeuds[i][0].size(); j++)
  43. {
  44. if(noeuds[noeuds[i][0][j]][1].size())
  45. {
  46. ok = 1;
  47. break;
  48. }
  49. }
  50. if(!ok && noeuds[i][0].size())
  51. {
  52. printf("NON\n");
  53. return 0;
  54. }
  55. }
  56. }
  57.  
  58. for(int i = 0; i < nbPersonnes; i++)
  59. {
  60. //if(i == 1)
  61. // printf("debug : ");
  62. int a = dfs(i, 1);
  63. if(noeuds[i][1].empty() && a >= nbConfig)
  64. {
  65. printf("NON\n");
  66. return 0;
  67. }
  68. //if(i == 1)
  69. // printf("%d\n", a);
  70. }
  71.  
  72. printf("OUI\n");
  73.  
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement