P9271 [CEOI2013] Splot 题解

cff_0102 · 2023-04-27 23:55:54 · 题解

由于停车图是递归定义的，因此有必要为问题找到递归公式。考虑串联和并联组合后，需要调用其他需要计算的函数。对于给定停车图的所有子图 G，计算对应的下面四个函数值，每个函数都代表的是可以停放在图 G 中的汽车总数（包括已经停在那里的汽车），使每辆停放的汽车都能以某种方式从 G 中出去。这些函数之间的区别主要在于汽车如何精确地从 G 中出去：

在上述所有函数中，可以使用特殊符号或数字（例如 -\infty）来表示对于已经停放在 G 中的车辆，怎么样都无法到达这种情况。

此外，为了使公式更简单，我们定义一个对于子图 G 的函数：

现在，需要为上述每个函数找到递归公式。这里详细解释了函数 \texttt{FORWARD} 的递归公式，并列出了其他函数的公式。大家可以自行验证其他公式。此外，会用到 \texttt{THROUGH}\le\texttt{FORWARD},\texttt{BACKWARD}\le\texttt{BOTH} 这个很容易推出的式子，来减少需要考虑的情况数量。这里重申一遍，每个函数都代表的是在这种情况下，可以停放在图 G 中的汽车总数。在下文中，五个函数分别简称为 \texttt{F,B,A,T,N}。

1. 如果该图只包含一个节点，则 \texttt{F,B,A} 的值始终为 1，而 \texttt{T,N} 的值要么为 0（如果这个节点没有车），要么为 -\infty（这个节点停了车）。
2. 假设我们串联 G_1,G_2 得到 G，并想要计算它的 \texttt{F} 函数值。有两种可能性：至少有一辆汽车停在 G_2 中，或者 G_2 为空。在第一种情况下，必须要有一条路径让 G_1 中的汽车全部在源点退出，因此，在此情况下最多可以停放的汽车数量为 \texttt{T(}G_1\texttt{)+F(}G_2\texttt{)}。在第二种情况下，最多可以停放的汽车数量是 \texttt{F(}G_1\texttt{)+N(}G_2\texttt{)}，因为 G_2 必须为空，并且 \texttt{F(}G_1\texttt{)} 给出了该情况下最佳的安排。
3. 现在，假设 G 是并联组合的结果，并且我们要计算函数 \texttt{F} 的值。并联组合更为复杂，因为我们还需要考虑新添加的源和终端是怎么样的。根据源和终端是否停了车，分为三种情况：
   1. 源被占用，终点空闲，此时，G_1 和 G_2 都必须为空。\texttt{F(G)} 的值为 1+\texttt{N(}G_1\texttt{)}+\texttt{N(}G_2\texttt{)}。
   2. 源和终点都是空闲的：现在，来自 G_1 和 G_2 的汽车可以直接向前退出，或者它们可以从其中一个的两侧退出，而另一个则具有从终端到汇点的路径。因此，\texttt{F(G)} 的值是 \texttt{F(}G_1\texttt{)}+\texttt{F(}G_2\texttt{)},\texttt{B(}G_1\texttt{)}+\texttt{T(}G_2\texttt{)},\texttt{T(}G_1\texttt{)}+\texttt{B(}G_2\texttt{)} 中最大的一个。
   3. 源空闲，终点被占用：其中一个子图必须要保证停在终点的车辆可以退出到源，而另一个子图的所有汽车都需要向前退出。因此，\texttt{F(G)} 的值为 1+\texttt{T(}G_1\texttt{)}+\texttt{F(}G_2\texttt{)},1+\texttt{F(}G_1\texttt{)}+\texttt{T(}G_2\texttt{)} 中更大的一个。

即使找到了递归计算函数的所有可能规则，由于需要考虑的情况数量巨大，实现（特别是重构最优排列时）仍然容易出错。一个寄巧可以极大地简化它的实现，那就是使用常量来定义上述递归规则，见下图。

上述表格将递归计算函数的规则编码为在 C++ 中的简单整数数组。例如，第二列中的 {FORWARD，0，1，THROUGH，FORWARD} 表示当 G 是 G_1 和 G_2 的并行组合，并且正在计算 \texttt{F} 函数时，我们需要考虑终点是否为空，终端是否被占用，G_1 的 \texttt{T} 值是多少，以及 G_2 的 \texttt{F} 值是几。

通过上述定义的常量，解决方案变得简单但仍然很长（不过还是好多了），需要实现一个解析器来将编码转换为类似树形结构的形式，然后需要递归遍历该树来计算每个函数。为了重构最优排列，我们需要记住用于获得相应函数最大值的规则索引。

下面是官方题解代码：

// CEOI 2013 - Task: Splot - Solution
// Author: Ante Derek

#include <cstdio>
#include <cassert>

using namespace std;

const int MAX = 1000000;
const int NEGINF = -(1<<28);
const int CFF_0102 = 542457;

enum FunctionType {FORWARD=0, BACKWARD=1, BOTH=2, THROUGH=3, NONE=4};

static const int S_RULE[][3] = {
  {FORWARD, FORWARD, NONE},
  {FORWARD, THROUGH, FORWARD},
  {BACKWARD, NONE, BACKWARD},
  {BACKWARD, BACKWARD, THROUGH},
  {BOTH, FORWARD, BACKWARD}, 
  {BOTH, BOTH, THROUGH},
  {BOTH, THROUGH, BOTH},
  {THROUGH, THROUGH, THROUGH},
  {NONE, NONE, NONE},
  {-1, -1, -1}
};

static const int P_RULE[][5] = {
  {FORWARD, 1, 0, NONE, NONE},
  {FORWARD, 0, 0, FORWARD, FORWARD},
  {FORWARD, 0, 0, THROUGH, BOTH},
  {FORWARD, 0, 0, BOTH, THROUGH},
  {FORWARD, 0, 1, THROUGH, FORWARD},
  {FORWARD, 0, 1, FORWARD, THROUGH},
  {BACKWARD, 0, 1, NONE, NONE},
  {BACKWARD, 0, 0, BACKWARD, BACKWARD},
  {BACKWARD, 0, 0, THROUGH, BOTH},
  {BACKWARD, 0, 0, BOTH, THROUGH},
  {BACKWARD, 1, 0, THROUGH, BACKWARD},
  {BACKWARD, 1, 0, BACKWARD, THROUGH},
  {BOTH, 1, 1, NONE, NONE},
  {BOTH, 1, 0, BACKWARD, BACKWARD},
  {BOTH, 0, 1, FORWARD, FORWARD},
  {BOTH, 0, 0, BOTH, BOTH},
  {THROUGH, 0, 0, THROUGH, BOTH},
  {THROUGH, 0, 0, BOTH, THROUGH},
  {NONE, 0, 0, NONE, NONE},
  {-1, -1, -1, -1}
};

class Splot {
  enum SplotType {NODE, SERIES, PARALLEL} type;
  int source;
  int sink;
  Splot *first;
  Splot *second;
  int result[5];
  int how[5];
  Splot(SplotType _type, 
        int _source=0, 
        int _sink=0,
        Splot* a = NULL,
        Splot* b = NULL):
    type(_type),
    source(_source),
    sink(_sink),
    first(a),
    second(b) {
    for (int i=0; i<5; i++)
      how[i] = result[i] = -1;    
  }
public:
  ~Splot() {
    if (first)
      delete first;
    if (second)
      delete second;
  }
  static Splot* new_node(char c) {
    return new Splot(NODE, c=='x', c=='x');
  }
  static Splot* new_series(Splot* a, Splot *b) {
    return new Splot(SERIES, 0, 0, a, b);
  }
  static Splot* new_parallel(char s, char t, Splot* a, Splot* b) {
    return new Splot(PARALLEL, s=='x', t=='x', a, b);
  }
  int node_result(int f) {
    if (f == FORWARD || f == BACKWARD || f == BOTH)
      return result[f] = 1;
    return result[f] = source?NEGINF:0;
  }
  Splot* rec_node(int f) const {
    if (f == FORWARD || f == BACKWARD || f == BOTH)
      return new_node('x');
    else
      return new_node('o');
  }
  int series_result(int f) {
    int &what = result[f];
    what = NEGINF;
    for (int l=0; S_RULE[l][0]!=-1; l++) {
      if (S_RULE[l][0] != f)
        continue ;
      int left = first->get_result(S_RULE[l][1]);
      int right = second->get_result(S_RULE[l][2]);
      if (left != NEGINF && right != NEGINF && left+right > what) {
        how[f] = l;
        what = left+right;
      }
    }
    return what;
  }
  Splot *rec_series(int f) const {
    int l = how[f];
    return new_series(first->reconstruct(S_RULE[l][1]), 
                      second->reconstruct(S_RULE[l][2]));
  }
  int parallel_result(int f) {
    int &what = result[f];
    what = NEGINF;
    for (int l=0; P_RULE[l][0]!=-1; l++) {
      if (P_RULE[l][0] != f)
        continue ;
      int news = P_RULE[l][1];
      int newt = P_RULE[l][2];
      if ((source && !news) || (sink && !newt))
        continue ;      
      int left = first->get_result(P_RULE[l][3]);
      int right = second->get_result(P_RULE[l][4]);
      if (left != NEGINF && right != NEGINF && left+right+news+newt > what) {
        how[f] = l;
        what = left+right+news+newt;
      }
    }
    return what;
  }
  Splot *rec_parallel(int f) const {
    int l = how[f];
    return new_parallel(P_RULE[l][1]?'x':'o',
                        P_RULE[l][2]?'x':'o',
                        first->reconstruct(P_RULE[l][3]), 
                        second->reconstruct(P_RULE[l][4]));
  }
  int get_result(int f) {
    if (result[f] != -1)
      return result[f];
    if (type == NODE) 
      return node_result(f);
    else if (type == SERIES)
      return series_result(f);
    else
      return parallel_result(f);
  }
  Splot* reconstruct(int f) const {
    if (type == NODE) 
      return rec_node(f);
    else if (type == SERIES)
      return rec_series(f);
    else
      return rec_parallel(f);
  }
  void print() const {
    if (type == NODE)
      printf("%c", source?'x':'o');
    else if (type == SERIES) {
      printf("S");
      first->print();
      second->print();
      printf("#");
    } else {
      printf("P%c|", source?'x':'o');
      first->print();
      second->print();
      printf("|%c#", sink?'x':'o');
    }
  }
};

class Parser {
  const char *s;
  int p;
  Splot* do_parse() {
    if (s[p] == 'o' || s[p] == 'x')
      return Splot::new_node(s[p++]);
    if (s[p] == 'S') {
      p++;
      Splot *first = do_parse();
      Splot *second = do_parse();
      p++;
      return Splot::new_series(first, second);
    }
    assert(s[p] == 'P');
    char sc = s[p+1];
    p += 3;
    Splot *first = do_parse();
    Splot *second = do_parse();
    char tc = s[p+1]; 
    p += 3;
    return Splot::new_parallel(sc, tc, first, second);
  }
 public:
  Parser(const char *_s):
    s(_s), p(0) {
  }
  Splot* parse() {
    assert(p == 0);
    Splot *r = do_parse();
    assert(s[p] == 0 || s[p] == '\n');
    return r;
  }
};

int main() {
  static char s[MAX+1];
  scanf("%s", s);
  Splot* splot = Parser(s).parse();
  int best = splot->get_result(FORWARD);
  printf("%d\n", best);
  Splot *filled = splot->reconstruct(FORWARD);
  filled->print();
  printf("\n");
  delete splot;
  delete filled;
  return 0;
}

最后附一份官方出题组的出题背景：