Guest User

Untitled

a guest
Dec 17th, 2018
108
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.49 KB | None | 0 0
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <stack>
  7. #include <bitset>
  8. #include <algorithm>
  9. #include <functional>
  10. #include <numeric>
  11. #include <utility>
  12. #include <sstream>
  13. #include <iostream>
  14. #include <iomanip>
  15. #include <cstdio>
  16. #include <cmath>
  17. #include <cstdlib>
  18. #include <ctime>
  19.  
  20. using namespace std;
  21.  
  22. const int oo = 1 << 28;
  23.  
  24. int n, m = 0;
  25. int c[1005][1005], f[1005][1005], d[1005], r[1005], color[1005], q[1005], p[1005];
  26. bool b[1005];
  27. int start, finish;
  28.  
  29. string name[1005];
  30.  
  31. bool ok(int i, int j){
  32.     if (d[i] == -1 || d[j] == -1)
  33.         return true;
  34.     if (abs(d[i]-d[j]) == 1)
  35.         return true;
  36.     return false;
  37. };
  38.  
  39. void dfs(int v, int g){
  40.     b[v] = true;
  41.     color[v] = g;
  42.     for (int i = 1; i <= n; i++)
  43.         if (!b[i] && c[v][i] == 1)
  44.             dfs(i, g ^ 1);
  45. };
  46.              
  47. int main() {
  48.  
  49.     freopen("in.in", "rt", stdin);
  50.    
  51.     cin >> n;
  52.     for (int i = 0; i < n; i++) {
  53.         string s1, s2;
  54.         int x, cur;
  55.         cin >> s1 >> s2 >> x;
  56.  
  57.             m++;
  58.             cur = m;
  59.             name[m] = s1;
  60.  
  61.         if (s2 == "anything") d[cur] = -1; else
  62.         if (s2 == "statements") d[cur] = 0; else d[cur] = 1;
  63.         r[cur] = x;
  64.     }  
  65.  
  66.     for (int i = 1; i <= n; i++)
  67.          for (int j = 1; j <= n; j++)
  68.       if (abs(r[i]-r[j]) == 2 && ok(i, j))
  69.         c[i][j] = c[j][i] = 1;     
  70.  
  71.     start = 0, finish = n + 1;
  72.     for (int i = 1; i <= n; i++)
  73.         if (!b[i]) dfs(i, 0);
  74.     for (int i = 1; i <= n; i++)
  75.         if (color[i]) c[start][i] = c[i][start] = 1;
  76.         else c[i][finish] = c[finish][i] = 1;
  77.  
  78.  
  79.     while (true){
  80.         for (int i = start; i <= finish; i++)
  81.             q[i] = -1, p[i] = -1;
  82.         int h = 0, t = 1;
  83.         q[0] = start, p[start] = start;
  84.         while (h < t) {
  85.             int cur = q[h++];
  86.             for (int i = 1; i <= finish; i++)
  87.                 if (p[i] == -1 && c[cur][i]-f[cur][i] > 0){
  88.                     q[t++] = i;
  89.                     p[i] = cur;
  90.                 }                
  91.         }
  92.         if (p[finish] == -1) break;
  93.         int cf = oo, cur = finish;
  94.         while (cur != p[cur]){
  95.             int prev = p[cur]; 
  96.             cf = min(cf, c[prev][cur] - f[prev][cur]);
  97.             cur = prev;
  98.         }      
  99.         cur = finish;
  100.         while (cur != p[cur]){
  101.             int prev = p[cur];
  102.             f[prev][cur] += cf, f[cur][prev] -= cf;
  103.             cur = prev;
  104.         }
  105.     }
  106.     int ans = 0;
  107.     for (int i = 1; i <= n; i++)
  108.         ans += f[start][i];        
  109.     printf("%d\n", ans);
  110.     for (int i = 1; i <= n; i++)
  111.         for (int j = 1; j <= n; j++)
  112.             if (f[i][j] == 1) {                                                          
  113.                 if (d[i] == 0 || d[j] == 1) cout << name[i] << " " << name[j]; else
  114.                 cout << name[j] << " " << name[i];
  115.                 puts("");
  116.             }
  117.     return 0;
  118. }
Add Comment
Please, Sign In to add comment