Guest User

Untitled

a guest
Jul 17th, 2015
311
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <deque>
  4. #include <cmath>
  5.  
  6. #define INF 10000
  7.  
  8. using namespace std;
  9.  
  10. struct person{
  11.     string name, skill;
  12.     int rank;
  13.     person(string Name, string Skill, int Rank){
  14.         name = Name; skill = Skill; rank = Rank;
  15.     }
  16. };
  17. vector <person> data;
  18. vector <vector <int> > g;
  19. const int MAXN = 2003;
  20. int c[MAXN][MAXN], f[MAXN][MAXN];
  21. int N;
  22. void readData(int &n){
  23.     cin >> n;
  24.     N = 2 * n + 2;
  25.     data.resize(n+1,person("0","0",0));
  26.     g.resize(N+1);
  27.     for (int i=1; i<=n; i++){
  28.         cin >> data[i].name;
  29.         cin >> data[i].skill;
  30.         cin >> data[i].rank;
  31.     }
  32. }
  33. void buildNetwork(int& n){
  34.     for (int i=1; i<=n; i++){
  35.         for (int j=1; j<=n; j++){
  36.             if (abs(data[i].rank - data[j].rank) == 2 && (data[i].skill == "anything" || data[j].skill == "anything" ||
  37.                 (data[i].skill == "statements" && data[j].skill == "testdata") || (data[i].skill == "testdata" && data[j].skill == "statements"))){
  38.                 g[i].push_back(j + n);
  39.                 g[j + n].push_back(i);
  40.                 c[i][j + n] = 1;
  41.             }
  42.         }
  43.     }
  44.     for (int i=1; i<=n; i++){
  45.         g[N-1].push_back(i);
  46.         g[i].push_back(N-1);
  47.         c[N-1][i] = 1;
  48.     }
  49.     for (int i=n+1; i<=2*n; i++){
  50.         g[i].push_back(N);
  51.         g[N].push_back(i);
  52.         c[i][N] = 1;
  53.     }
  54. }
  55. bool bfs(int v, deque <int>& turn, vector <int>& lvl){
  56.     int q,to;
  57.     for (q=0; q<g[v].size(); q++){
  58.         to = g[v][q];
  59.         if (c[v][to] - f[v][to] > 0 && lvl[to] == INF){
  60.             lvl[to] = lvl[v] + 1;
  61.             turn.push_back(to);
  62.         }
  63.     }
  64.     turn.pop_front();
  65.     if (!turn.empty()) bfs(*turn.begin(),turn,lvl);
  66.     return lvl[N] != INF;
  67. }
  68. int dfs(int v, vector <int>& pointer, vector <int>& lvl){
  69.     if (v == N){
  70.         return 1;
  71.     }
  72.     int q,to;
  73.     for (q=pointer[v]; q<g[v].size(); q++){
  74.         to = g[v][q];
  75.         if (lvl[v] + 1 == lvl[to] && c[v][to] - f[v][to] > 0 && dfs(to,pointer,lvl)){
  76.             f[v][to] += 1;
  77.             f[to][v] -= 1;
  78.             return 1;
  79.         }
  80.         else{
  81.             pointer[v]++;
  82.         }
  83.     }
  84.     return 0;
  85. }
  86. void findMaxFlow(int &n){
  87.     deque <int> turn;
  88.     vector <int> lvl(N+1);
  89.     vector <int> pointer(N+1);
  90.     while (1){
  91.         turn.push_back(N-1);
  92.         lvl.assign(N+1,INF);
  93.         lvl[N-1]=0;
  94.         if (!bfs(N-1,turn,lvl)) break;
  95.         pointer.assign(N+1,0);
  96.         while (dfs(N-1,pointer,lvl));
  97.     }
  98.     int pairs = 0;
  99.     for (int i=1; i<=n; i++){
  100.         for (int j=n+1+i; j<=2*n; j++){
  101.             if (f[i][j] == 1){
  102.                 pairs++;
  103.             }
  104.         }
  105.     }
  106.     cout << pairs << "\n";
  107.     for (int i=1; i<=n; i++){
  108.         for (int j=n+1+i; j<=2*n; j++){
  109.             if (f[i][j] == 1){
  110.                 if (data[i].skill != "testdata" && data[j - n].skill != "statements") cout << data[i].name << " " << data[j - n].name << "\n";
  111.                 else cout << data[j - n].name << " " << data[i].name << "\n";
  112.             }
  113.         }
  114.     }
  115. }
  116. int main(){
  117.     freopen("input.txt","r",stdin);
  118.     freopen("output.txt","w",stdout);
  119.     int n;
  120.     readData(n);
  121.     buildNetwork(n);
  122.     findMaxFlow(n);
  123.     return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment