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

bitset玄学完美优化复杂度？

题目描述

参加jsoi冬令营的同学最近发现，由于南航校内修路截断了原来通向计算中心的路，导致去的路程比原先增加了近一公里。而食堂门前施工虽然也截断了原来通向计算中心的路，却没有使路程增加，因为可以找到同样长度的路作替代。其实，问题的关键在于，路截断的地方是交通要点。

同样的情况也出现在城市间的交通中。某些城市如果出了问题，可能会引起其他很多城市的交通不便。另一些城市则影响不到别的城市的交通。jsoi冬令营的同学发现这是一个有趣的问题，于是决定研究这个问题。

他们认为这样的城市是重要的：如果一个城市c被破坏后，存在两个不同的城市a和b（a, b均不等于c），a到b的最短距离增长了（或不通），则城市c是重要的。

jsoi冬令营的同学面对着一张教练组交给他们的城市间交通图，他们希望能找出所有重要的城市。现在就请你来解决这个问题。

输入输出格式

输入格式：

第一行两个整数N,M,N为城市数，M为道路数。

接下来M行，每行三个整数，表示两个城市之间的无向边，以及之间的路的长度。

输出格式：

一行，按递增次序输出若干的数，表示重要的城市。

如果没有点的话需要输出一行

“No important cities.”

去掉引号。

输入输出样例

输入样例#1：

4 4

1 2 1

2 3 1

4 1 2

4 3 2

输出样例#1：

2

说明

30%的数据：$N\le 20$；

60%的数据：$N\le 100$；

100%的数据：$N\le 200,M\le \frac{N\times (N-1)}{2},0<c\le 10000$。$c$即路的长度。

保证不出现重边和自环

感谢@赵昕鹏 和@qq2477259579 提供程序

题解：

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

重要城市

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

因此我们可以开一个三维数组$im[i][j][k]$表示k在$latex 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$省掉，或者说优化一点呢？

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

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

因此bitset中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;

}