Recruiting

题目描述

Hurry! Two well-known software companies are recruiting programmers. Initially the total number of unemployed programmers is $n$. The companies are hiring them one by one, alternately. In one turn a company hires one of the programmers who has not been hired yet. The first company starts hiring.

Furthermore, there are some pairs of friends among the programmers. Of course, a programmer may have several friends. Friendship is a symmetrical relationship, so if $a$ is a friend of $b$ then $b$ is a friend of $a$.

All such pairs are known to the companies, and the companies follow the rule: a new programmer hired by a company must have at least one friend among the programmers already working in this company. The only exception is a programmer that a company starts with, he can be chosen arbitrarily. It may happen that after a number of turns a company can not longer hire anyone else according to the rule. In this case it stops hiring, while the other company can continue.

As usual, not all the programmers are created equal. There are three geniuses among them, and each company wants to hire as many geniuses as possible. Note that each company always can guarantee one genius to itself starting with a genius. So the question is, which company will hire two geniuses, if they both use optimal strategies.

Note that both companies have the full information during the hiring: friendship relations, who are geniuses and which programmers were hired by each company in each turn.

题意概述

给定一张$n$个点$m$条边的无向图。两个人轮流选点。每个人的第一个点可以任意选，接下来每次都必须从与自己已选的点相邻的点中选一个。不能选已被选的点。若某一轮中某人不存在满足条件的点，则他这一轮不选。已知$1$、$2$、$3$号点是重要点，两人都想尽可能多地选到重要点。问在最优策略下，谁能选到更多的重要点。保证不会平局。

数据范围：$3 \le n \le 10^5, \ 2 \le m \le 2 \times 10^5$。

算法分析

易知不用考虑不能选已被选的点这个条件，因为这样一定不优。

令$d_{i, j}$表示$i$号点和$j$号点之间最短路径的长度。那么先手必胜当且仅当

$$
\exists i, \ \forall j, \ \sum_{k=1}^3 [d_{k, i} \gt d_{k, j}] \lt 2
$$

考虑它的意义。对于$i$号点，若存在一个$j$号点使得$i$号点到某两个重要点的距离严格大于$j$号点到这两个点的距离，则先手不能选$i$号点；否则，先手选$i$号点必胜。证明略。

所以只要枚举$i, j$就能判断。事实证明，稍加剪枝后的枚举可以通过此题。

代码

#include <cstdio>
#include <cstring>

static int const N = 100005;
int ne, h[N], d[3][N], que[N];
struct Edge {
  int v, nxt;
} e[N << 2];

void add_edge(int u, int v) {
  e[++ne] = (Edge){v, h[u]}, h[u] = ne;
  e[++ne] = (Edge){u, h[v]}, h[v] = ne;
}

void get_d(int s, int *d) {
  int qb = 0, qe = 1;
  d[s] = 0, que[0] = s;
  for (; qb < qe;) {
    int u = que[qb++];
    for (int i = h[u]; i; i = e[i].nxt)
      if (d[e[i].v] > d[u] + 1)
        d[e[i].v] = d[u] + 1, que[qe++] = e[i].v;
  }
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0, u, v; i < m; ++i)
    scanf("%d%d", &u, &v), add_edge(--u, --v);
  memset(d, 0x3f, sizeof d);
  for (int i = 0; i < 3; ++i)
    get_d(i, d[i]);
  bool flag = 0;
  for (int i = 0; !flag && i < n; ++i) {
    bool ls = 1;
    for (int j = 0; ls && j < n; ++j) {
      int cnt = 0;
      for (int k = 0; k < 3; ++k)
        cnt += d[k][i] > d[k][j];
      ls &= cnt < 2;
    }
    flag |= ls;
  }
  puts(flag ? "1" : "2");
  return 0;
}