题解【P7026 [NWRRC2017]Hidden Supervisors】

command_block · 2021-10-20 20:59:20 · 题解

鱼大博客长长长，暂且没看，自己做出来了，感动（

题意：给定一个 n 个点的内向森林，其中 1 号点为某个树的根。

你需要将这个森林连成一棵以 1 为根的有根树，并使得最终树（对应的无根树）的最大匹配尽可能大。

------------ 最终方案显然是除了 $1$ 外每个根连出一条边。 ------------ - **树上最大匹配的贪心** ：从深往浅考虑，每个点若能匹配父亲则匹配。注意，若占用根的最大匹配和不占根的最大匹配大小相同，贪心会得出不占根的方案。我们考虑逐棵树考虑根的连边情况，且要求新的小树 $T'$ 必须连接到 $1$ 所在的大树 $T$ 上。假设我们已经确定了一种树的排列，如何构造最优的方案。（显然每种方案都能对应一种排列）记准备接到大树 $T$ 上的小树为 $T'$。记 $\max(T)$ 为 $T$ 的最大匹配。由于只加了一条边，连接后最大匹配的上界显然为 $\max(T)+\max(T')+1$ 。观察连接之后贪心的形为。由于贪心从浅到深考虑，$T'$ 内部的匹配不会变化。记 $T'$ 的根为 $t$ 。 - $\max(T')$ 含 $t

此时新边的深端（T' 的根）已经被占用，故新边一定不会被选中。T,T' 原有的匹配均保持。

\max(T')$ 不含 $t
容易想到，若 T 中存在非匹配点，则将 t 与之连接，能多出一个匹配边。这已经达到上界。

否则，若 T 中不存在非匹配点，考虑点集 T\cup\{t\} ，它们之中的匹配才可能变化。但现在满匹配仅多加一个点，显然匹配不可能增大。

综上，我们证明了：

加入 T' 时，若 T' 的根为非匹配点，且 T 中存在非匹配点 v ，则连接 (t,v) 并使匹配加一。

若条件不满足，匹配不可能增大，为避免影响匹配情况（不便考虑），直接令 t 与 1 相连，不难发现此时可以认为贪心算法不会改动匹配。

观察如上算法的行为：

记顺序为 T_{1\sim m} ，其中 T_1 肯定是 1 所在的树。
对于 $T_2$ ，若根非匹配，选择一个非匹配点连接。若根已匹配，或找不到非匹配点，则弃疗，直接连向 $1$ 。不要忘记添加新的非匹配点。

接下来进一步考虑：何种顺序才是最优的？

我们的目标是尽量让更多的树加入时能新增匹配，这和现存的非匹配点有关。不难想到经典的贪心：根已匹配的树无要求，先直接圈接入，接下来在根非匹配的树中，让非匹配点更多的树打头阵。

#include<algorithm>
#include<cstdio>
#include<vector>
#define MaxN 100500 
using namespace std;
vector<int> p[MaxN],g[MaxN];
int st[MaxN],tn;
bool vis[MaxN];
void dfs(int u,int fa)
{
    for (int i=0;i<g[u].size();i++)dfs(g[u][i],u);
    if (!vis[u]&&!vis[fa])vis[u]=vis[fa]=1;
    if (!vis[u])st[++tn]=u;
}
int a[MaxN],fa[MaxN],nrt,w[MaxN];
bool cmp(int A,int B){return w[A]>w[B];}
int main()
{
  int n;scanf("%d",&n);
  for (int i=2;i<=n;i++){
    scanf("%d",&fa[i]);
    if (fa[i])g[fa[i]].push_back(i);
  }
  vis[0]=1;
  int ans=0;
  for (int u=1;u<=n;u++)if (!fa[u]){
        tn=0;
        dfs(u,0);
        ans+=tn;
        for (int i=1;i<=tn;i++)p[u].push_back(st[i]);
        w[u]=(vis[u] ? n+1 : p[u].size());
        a[++nrt]=u;
    }
  ans=(n-ans)/2;
  w[1]=n+2;
  sort(a+1,a+n+1,cmp);
  tn=0;
  for (int i=0;i<p[1].size();i++)st[++tn]=p[1][i];
  for (int k=2;k<=n;k++){
    int u=a[k];
    while(tn&&vis[st[tn]])tn--;
    if (!vis[u]&&tn){vis[u]=1;vis[fa[u]=st[tn]]=1;ans++;}
    else fa[u]=1;
    for (int i=0;i<p[u].size();i++)st[++tn]=p[u][i];
  }
  printf("%d\n",ans);
  for (int i=2;i<=n;i++)printf("%d ",fa[i]);
    return 0;
}

题解 【P7026 [NWRRC2017]Hidden Supervisors】

题解【P7026 [NWRRC2017]Hidden Supervisors】