题解：P7086 [NWRRC 2013] Heavy Chain Clusterization

· · 题解

食用博客体验感更佳其实并没有。

题目大意

给定 n 个字符串，求能够分成几份字符串集合，每份中的所有字符串都存在长度为 k 的前缀或后缀相同。

题目变形

  1. 我们根据观察发现，一个字符串被分到某一个字符串集合中有三种可能，其中，单独成一个集合我们可以认为他被孤立了，等到时候再做特殊处理。题目特别说明没有相同字符串，加上 k 是一个定值，也就是任何字符串的长度为 k 的前后缀恒定。

  2. 因而，我们可以将字符串抽象成一条边，而对应的两种可能便以前后缀的点权形式在其两端，而具有相同前缀或后缀的字符串共点，整个问题就成了一个无向图的问题。

由于一条无向边只会连接前后缀，因而我们很容易就将整个图划分为两部分：前缀和后缀，而因为不会有边连接前缀和前缀或者后缀和后缀，因而整张图的这两部分各自内部无连边，也就是整幅图为二分图。

  1. 题目要我们划分集合，集合内的字符串（无向边）都共点，且都共前缀或者后缀。

  2. 站在一条边的角度，他要么加入前缀的集合，要么加入后缀的集合，单独成一组可以理解为他可以加入任意一个集合，或者两者都加入，将其平常化。

  3. 这时，就出现了至少二选一的特性，结合本图是一张二分图，因而，题目要求的就是二分图最小点覆盖。

引申

二分图最小点覆盖等于二分图最大匹配的证明，这里不再赘述，如有不知道或者感兴趣的，请移步这里。

重点做法

寻找方案

这道题的难点之一就是如何输出二分图最小点覆盖的边的方案，如下图（我这里特意分了左右部，方便查看）：

假设二分图最大匹配匹配了 1 \to 4,3 \to 2,5 \to 6 三条。

步骤如下：

  1. 先从右部的一个没有匹配的点 x 出发，由于二分图最大匹配中，此点所连的边没有拿下匹配边的资格，因而选择 x 为二分图最大点覆盖显然不值。

  2. 但是，这一条边又必须覆盖到，因而他所连的边的端点 y 必须选入（可能不止一个 y 点）。

  3. 而因为 y 点被选入了，因而他所连的边的 z 点无需选入（同样可能不止一个也可能没有）。

  4. 重复 1 \to 3 步骤，直至被选完为止。

但是，像上图中由 5,6,7 三点组成的连通块并未算入，是因为右部 6 号点已经有匹配点了，但是整个连通块只有他一个右部点（不一定所有图出现这种情况右部都只有一个点，重点是“都有匹配点”）。

在这种情况之下，我们要清楚以下几点：

  1. 右部点一定小于等于左部点，因为右部点都已经都有匹配点了，说明左部点至少有右部点那么多个点来做匹配点。

  2. 由于右部点都已经有匹配点了，因而选择左部的点不一定最优，但是全选右部的点一定最优，并且能覆盖所有的边，而且，右部点数量小于等于左部点数量。

因而，我们可以再扫一遍，寻找已经匹配了但是又未按上述步骤找到的右部点，将其纳入二分图最小点覆盖的选点中。

输出方案

根据二分图最小点覆盖的定义，只要输出与其相邻的边就可以了。

由于无向边一定是连接着前缀和后缀，所以与一个点接壤的所有边一定能在一个集合内。

同时，这样做根据定义，也不会遗漏任何一条边。

但是，如果遇上下面的情况：

此时选的是 3,4 两点，正好是同一条边的两个端点，因而按照上述做法，需要判重。

部分代码

cin >> n >> k;
for(int i = 1; i <= n; i++)
{
    cin >> s[i];
    string st = s[i].substr(0, k);
    if(!Mapst[st])
        Mapst[st] = ++cntst; // 前缀 
}
cnted = cntst; // 错开编号，因为是双向边，同时防止编号冲突 
for(int i = 1; i <= n; i++)
{
    string st = s[i].substr(0, k), ed = s[i].substr(s[i].size() - k);
    if(!Maped[ed])
        Maped[ed] = ++cnted; // 后缀 
    nbr[Mapst[st]].push_back((node){Maped[ed], i});  // 双向边 
    nbr[Maped[ed]].push_back((node){Mapst[st], i}); 
}
for(int i = 1; i <= cntst; i++) // 匈牙利 
    if(hungary(i, ++tim))
        ans++;
for(int i = cntst + 1; i <= cnted; i++) // 第一遍找寻答案 
    if(!mth[i] && !vis[i])
        dfs(i, 1, tim);
for(int i =  1; i <= cnted; i++) // 第二遍扫描 
    if(mth[i] && !vis[i])
        Tsn[i] = 1; // Tsn[i]表示第i个点有没有被选上

内容较为通俗，可能并不严谨，望众位指出错误，谢谢！