Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdlib>
- #include <algorithm>
- #include <cstdio>
- #include <vector>
- int nbPersonnes, nbVelos, nbReq;
- std::vector<int> noeuds[2000][2];
- int dfs(int noeud, int last)
- {
- int maxi = 0;
- for(int i = 0; i < noeuds[noeud][!last].size(); i++)
- maxi = std::max(maxi, dfs(noeuds[noeud][!last][i], !last) + last);
- return maxi;
- }
- int main()
- {
- int nbConfig = 0;
- scanf("%d%d%d", &nbPersonnes, &nbVelos, &nbReq);
- for(int i = 0; i < nbReq; i++)
- {
- int a, b, ut;
- scanf("%d%d%d", &a, &b, &ut);
- b+=nbPersonnes;
- noeuds[a][ut].push_back(b);
- noeuds[b][ut].push_back(a);
- nbConfig += ut;
- }
- for(int i = 0; i < nbPersonnes+nbVelos; i++)
- {
- if(noeuds[i][1].empty())
- {
- char ok = 0;
- for(int j = 0; j < noeuds[i][0].size(); j++)
- {
- if(noeuds[noeuds[i][0][j]][1].size())
- {
- ok = 1;
- break;
- }
- }
- if(!ok && noeuds[i][0].size())
- {
- printf("NON\n");
- return 0;
- }
- }
- }
- for(int i = 0; i < nbPersonnes; i++)
- {
- //if(i == 1)
- // printf("debug : ");
- int a = dfs(i, 1);
- if(noeuds[i][1].empty() && a >= nbConfig)
- {
- printf("NON\n");
- return 0;
- }
- //if(i == 1)
- // printf("%d\n", a);
- }
- printf("OUI\n");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement