SRM549 Div2 Medium

500

マッチング。

view plainprint?

1. const int TOP = 100 + 5;  
2. const int BOT = 100 + 5;  
3.   
4. const int N = TOP + BOT + 5;  
5.   
6. vector<int> g[N];  
7.   
8. int match[N];  
9. bool vis[N];  
10.   
11. bool rec(int curr)  
12. {  
13.   vis[curr] = true;  
14.   for (int i = 0; i < g[curr].size(); ++i) {  
15.     int next = g[curr][i];  
16.     int w = match[next];  
17.     if (w < 0 || (!vis[w] && rec(w))) {  
18.       match[curr] = next;  
19.       match[next] = curr;  
20.       return true;  
21.     }  
22.   }  
23.   return false;  
24. }  
25.   
26. int matching(int n)  
27. {  
28.   int f = 0;  
29.   fill(match, match + N, -1);  
30.   for (int i = 0; i < n; ++i) {  
31.     if (match[i] < 0) {  
32.       fill(vis, vis + N, false);  
33.       f += rec(i);  
34.     }  
35.   }  
36.   return f;  
37. }  
38.   
39. class PointyWizardHats {  
40. public:  
41.   int getNumHats(vector <int> tH,  
42.                  vector <int> tR,  
43.                  vector <int> bH,  
44.                  vector <int> bR)  
45.   {  
46.     fill(g, g + N, vector<int>());  
47.     fill(vis, vis + N, false);  
48.   
49.     const int T = tH.size();  
50.     const int B = bH.size();  
51.   
52.     const double eps = 1e-8;  
53.   
54.     for (int i = 0; i < T; ++i) {  
55.       for (int j = 0; j < B; ++j) {  
56.         double tA = (double)tR[i] / sqrt(tR[i] * tR[i] + tH[i] * tH[i]);  
57.         double bA = (double)bR[j] / sqrt(bR[j] * bR[j] + bH[j] * bH[j]);  
58.         if (tA + eps < bA && tR[i] < bR[j]) {  
59.           int a = i;  
60.           int b = j + TOP;  
61.           g[a].push_back(b);  
62.           g[b].push_back(a);  
63.         }  
64.       }  
65.     }  
66.   
67.     return matching(T);  
68.   }  
69. };  

const int TOP = 100 + 5;
const int BOT = 100 + 5;

const int N = TOP + BOT + 5;

vector<int> g[N];

int match[N];
bool vis[N];

bool rec(int curr)
{
  vis[curr] = true;
  for (int i = 0; i < g[curr].size(); ++i) {
    int next = g[curr][i];
    int w = match[next];
    if (w < 0 || (!vis[w] && rec(w))) {
      match[curr] = next;
      match[next] = curr;
      return true;
    }
  }
  return false;
}

int matching(int n)
{
  int f = 0;
  fill(match, match + N, -1);
  for (int i = 0; i < n; ++i) {
    if (match[i] < 0) {
      fill(vis, vis + N, false);
      f += rec(i);
    }
  }
  return f;
}

class PointyWizardHats {
public:
  int getNumHats(vector <int> tH,
                 vector <int> tR,
                 vector <int> bH,
                 vector <int> bR)
  {
    fill(g, g + N, vector<int>());
    fill(vis, vis + N, false);

    const int T = tH.size();
    const int B = bH.size();

    const double eps = 1e-8;

    for (int i = 0; i < T; ++i) {
      for (int j = 0; j < B; ++j) {
        double tA = (double)tR[i] / sqrt(tR[i] * tR[i] + tH[i] * tH[i]);
        double bA = (double)bR[j] / sqrt(bR[j] * bR[j] + bH[j] * bH[j]);
        if (tA + eps < bA && tR[i] < bR[j]) {
          int a = i;
          int b = j + TOP;
          g[a].push_back(b);
          g[b].push_back(a);
        }
      }
    }

    return matching(T);
  }
};