题解 P1841 【[JSOI2007]重要的城市】bitset题解

· · 题解

我的blog传送门：wjyyy

因为Floyd是一种玄学DP思想，所以它的状态更新来源有很多，在这个题里需要整理出它的阶段性与转移，看上去十分麻烦。而我们如果把Floyd当作最短路算法中的松弛，就是相当于在把两段最短路拼接在一起，拥有它们合在一起的性质。

重要城市

   重要城市就是如果这个点被删掉，那么最短路的长度就会改变。因此这个点一定在最短路上。而当两点间的最短路有多条时，它们上的点不一定都是重要城市，经过分析我们可以这样理解：设(u,v)间最短路条数为k，重要城市为p，那么这k条最短路一定都经过点p。用反例来说明，就是如果不是k条最短路都经过点p，那么去掉点p，还有剩下的最短路可以走，则不合法。

   因此我们可以开一个三维数组\mathrm{im[i][j][k]}表示k在i,j的几条最短路上。而我们用floyd做最短路计数也比较方便，一旦k所在的最短路数量与(i,j)间的最短路数量相同，那么k就一定是一个重要城市，判断条件为im[i][j][k]==cnt[i][j]\Rightarrow k是重要城市。

   在上图中，1→8最短路计数为3，其中除了起点和终点，被经过了3次的点的点有2和7，因此它们是这条路径上的重要城市。

   因为floyd的时间复杂度为O(N^3)，而每次更新还要循环一个N，因此总时间复杂度为O(N^4)。

bitset优化

   我们在上面提到，状态合并/更新需要额外枚举一个O(N)，我们可不可以把这个N省掉，或者说优化一点呢

   这时可以考虑\mathrm{bitset}，\mathrm{bitset}可以使常数优化32倍，这个题的N规模才200，优化一个32就快把一个N变成一个\log N了，这个题的数据规模还是可以承受的。不过\mathrm{bitset}存的是二进制啊，可是上面提到的数组存的是计数啊。

   我们可以换一个方式想想，如果这两个点之间已经找到了4条最短路，其中有3条经过点p，那此时p已经不合法了，就直接把它置为0，以后尽管所有路径都经过p，它也不可能是关键城市。

   因此\mathrm{bitset}中\mathrm{im[i][j][k]}里面存的是，现有状态下，k是不是i到j最短路上的关键城市。当更新（松弛）最短路时，关键城市是两段最短路上的关键城市之并集；而更新最短路计数，也就是找到了一条新的最短路时，如上图，就要取交集，因为一个城市只有在两点间任何一条最短路上都存在，才能作为这两点间的关键城市。而交集并集在位运算中就是and(&)和or(|)，而点集有200，普通的位运算完成不了，就让bitset来做。

   在一开始初始化时，把两个连接在一起的点上的关键城市设为两个端点，在floyd“松弛”最短路时，直接把两段最短路的关键城市“拼起来”，就是新的最短路上的关键城市。最后判断用O(N^3)遍历，看一个点是否为某两个点之间的关键城市，不过要注意不能与这两个点重合，因为为了方便，一开始我们把起点和终点也定为关键城市（符合关键城市的一般定义）。

   因此这道题的总复杂度为O(\frac{N^4}{32}+N^3)

Code：

#include<cstdio>
#include<cstring>
#include<bitset>
using std::bitset;
bitset<210> im[210][210];
int f[210][210];
int is[210];
int main()
{
    memset(f,0x3f,sizeof(f));
    int u,v,n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        f[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&u,&v);
        scanf("%d",&f[u][v]);
        f[v][u]=f[u][v];
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            im[i][j][i]=1;//初始化设两端为重要城市
            im[i][j][j]=1;
        }

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(f[i][k]+f[k][j]==f[i][j])
                    im[i][j]&=(im[i][k]|im[k][j]);//当更新计数时取交集
                else if(f[i][k]+f[k][j]<f[i][j])//当更新最短路时直接赋值为两段的并集
                {
                    f[i][j]=f[i][k]+f[k][j];
                    im[i][j]=im[i][k]|im[k][j];
                }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                if(k!=i&&k!=j)//注意特判
                    if(im[i][j][k])
                        is[k]=1;
    int flag=0;
    for(int i=1;i<=n;i++)
        if(is[i])
        {
            flag=1;
            printf("%d ",i);
        }
    if(!flag)//注意判断无解
        puts("No important cities.");
    return 0;
}