题解 P5441 【XR-2】伤痕

· · 题解

xht的神仙题解

一，初探问题

首先，我们知道一共需要建造\dfrac{n(n-1)}{2}条道路，而其中最多有n条双向道。

容易看出，多建双向道对选择方案数的增多是有益的，因此我们将造满n条双向道，剩下的只能造单向道了。

这样的话，有多少单向道呢？

\dfrac{n(n-1)}{2}-n=\dfrac{n(n-3)}{2}

另一方面，我们把任意四个城市放在一起，称为一组。

一个组可能有两种情况：所有城市可以自由相互到达（意味着你可以从任何一个城市出发去向组中任何另一个城市，并且还能回来）或是不然。

显然，国王选出的四个核心城市组成的一组应是上述中的前者（我们就把它称为强连通组吧，反之就是非强连通组）。

对于所有的n座城市我们从中任意选出四个来组成一组，有C^4_n种不同的选法。

对于其中所有的强连通组，都是可行的核心城市选择方案。因此我们应该尽量减少这C^4_n个组中非强连通组的个数。

二，非强连通组的分类

看以下三张图（球带表城市，黑线为单向道，绿线为双向道，灰线为不确定的道路）：

从蓝色球带表的城市进入红色球带表的城市后，便无法回到蓝色球，因此它们都是非强连通组的可能情况。

事实上，不存在一个非强连通组不属于上述三种情况中的一种，因为非强连通组无非就是存在进去却回不来的城市或是根本就进不去的城市，而上述图已经表示了这样城市的全部可能产生原因。

由此我们将非强连通组进行一下分组。

第一类非强连通组：

满足图一情况（一个城市向其它三个城市发单向道）的组为第一类非强连通组。

第二类非强连通组

满足图二情况（其它三个城市向一个城市发单向道）但不满足图一情况的组为为第二类非强连通组。

注意有的组既满足图一又满足图二：

它应为第一类。

第三类非强连通组

满足图三情况（两个城市连双向道，另外两个也连双向道，前两个分别向后两个连单向道）的组为第三类非强连通组。

容易看出这三类组互相没有重叠，这意味这我们成功将非强连通组进行了分类。

接下来我们要尝试尽量减少这三类非强连通组的数量。

三，减少第一类组：用数学来分析

对与一个城市 i ，设它有 S_i 条向外的单向道。

如果 S_i \geqslant 3 ,那么该城市就可以与它发出单向道的城市中的三个组成一个第一类组，不同的第一类组的数量为 C^3_{S_i}。

从而所有的第一类组的数量为 \sum_{i=1}^n C^3_{S_i}

另一方面我们已经知道所有的单向道总数为 \dfrac{n(n-3)}{2}，即

\sum_{i=1}^n S_i =\dfrac{n(n-3)}{2}

现在记 f(x)=C^3_x

那么我们的问题成为了：

已知 S_1+S_2+...+S_n=\dfrac{n(n-3)}{2} ，求 f(S_1)+f(S_2)+...+f(S_n)的最小值。

为了解决它，我们先考虑 f(x) 的特点。有：

f(x)=C^3_x=\dfrac{x(x-1)(x-2)}{6} f'(x)=\dfrac{3x^2-6x+2}{6} f''(x)=x-1 ![](https://cdn.luogu.com.cn/upload/image_hosting/mx17u243.png) 当 $x\geqslant2$ 时其显然为凸函数（图像下凸）。 对于凸函数 $f(x)$ 有这样的性质：若 $p+q$ 为常数，则 $p$ 与 $q$ 间的差值越小， $f(p)+f(q)$ 越小。 可借下图理解： ![](https://cdn.luogu.com.cn/upload/image_hosting/l4e0jg4o.png) （图中有$p_1+q_1=p_2+q_2$,由于$p_2$和$q_2$间的差距较小，$f(p_2)+f(q_2)<f(p_1)+f(q_1)$,图中用二者的一半来比较大小） 由此，我们可以知道若想让$f(S_1)+f(S_2)+...+f(S_n)$最小，只需使 $S_1$ , $S_2$ , ... , $S_n$ 间差距最小。 那我们就让它们都相等，即 $S_1=S_2=...=S_n=\dfrac{\sum_{i=1}^n S_i}{n}=\dfrac{n-3}{2}

这样第一类组就会最少。数量为:

n\times C_{\frac{n-3}{2}}^3=\dfrac{n(n-3)(n-5)(n-7)}{48}

接下来考虑第二类组和第三类组。

四，减少第二和第三类组：构造

事实上，一个特别的构造可在完成三中要求的同时将第二类和第三类组降到最少。

问：那么它们两个最少是有多少呢？

答：最少可以没有。

没错，下面这个构造可以保证不出现第二类和第三类组。

下面是这个构造的两个实例：

看上去很有意思，你会发现这两个图形都是中心对称的，保证了 S_1=S_2=...=S_n ，同时其顺时针的单向道建造方案使第二类组和第三类组不会出现。

到底是如何构造的呢？

简单的说，就是将 n 个城市放在正 n 边形的顶点上，所有顶点相互连线，将所有最长对角线设为双向道（当 n 为奇数时，正 n 边形有 n 条最长对角线），其它线按顺时针方向建为单向道。

考虑到一个顶点要向外连 (n-1) 条线，而最长对角线为最中间两条，即第 \dfrac{n-1}{2} 条和第 \dfrac{n+1}{2} 条，第 1 条到第 \dfrac{n-3}{2} 条它要向外连单向道，第 \dfrac{n+3}{2} 条到第 (n-1) 条是其它点向它连的单向道。

构造方法也可说为：一个城市向接下来的 \dfrac{n-3}{2} 个点连单向道，向接下来的第 \dfrac{n-1}{2} 和第 \dfrac{n+1}{2} 个点连单向道。

接下来证明一下这个构造方法的一些性质：

1，它满足每个城市向外的单向道数量相等，即 S_1=S_2=...=S_n=\dfrac{n-3}{2}

由构造方法可知每个城市会向接下来的 \dfrac{n-3}{2} 个城市连单向道，此说法显然成立。

2，第二类组不会出现。

我们知道，由于一个顶点向外连线中第 \dfrac{n+3}{2} 条到第 (n-1) 条是其它点向它连的单向道（共有 \dfrac{n-3}{2} 条），当 n\geqslant 3 时就会出现二中图二的情况：三个城市向一个城市连单向道，但是这不是第二类组，因为图一的情况也会出现，如图:

一个篮球和两个绿球向红球连单向边，但顺时针方向最前面的篮球也会向两个绿球连单向边，根据“同时满足图一和图二的组为第一类组”可知此为第一类组。

3，第三类组不会出现

第三类组中会出现有两个连着双向道的的城市同时向一个城市连单向道的情况。

但是考虑到一个顶点向外连边中开始的几条才为向外单向道，中间的为双向道，因此 它连向外单向道的顶点 会在顺时针方向上 它连双向道的顶点 的前面，这意味着 双向道的另一边的顶点 无法向 它连单向道的顶点 连单向道，如图：

最后，由于不会出现第二类和第三类组，我们只需将组的总数减去第一类组的数量就可以得到最终答案：

C^4_n-n\times C_{\frac{n-3}{2}}^3=\dfrac{n(n-1)(n-2)(n-3)}{24}-\dfrac{n(n-3)(n-5)(n-7)}{48}=\dfrac{n(n-3)(n^2+6n-31)}{48}

五，代码

#include<iostream>
using namespace std;
int n,c[100][100];
int main()
{
    cin>>n;
    if (n==1)
    {
        cout<<0<<endl<<0;
        return 0;
    }//特判n=1时的情况 
    cout<<n*(n-3)*(n*n+6*n-31)/48<<endl;
    for (int i=1;i<=n;++i)
    for (int j=i+1;j<=i+(n+1)/2;++j)
    c[i][(j-1)%n+1]=1;
    //这里连边时将单向道和双向道一起处理了
    //原因是双向道可以看成两条单向道 
    for (int i=1;i<=n;++i)
    {
        for (int j=1;j<=n;++j)
        cout<<c[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}