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

作者: wjyyy 分类: bitset,floyd,数据结构,解题报告 发布时间: 2018-08-04 16:22

点击量:25

 

    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在\(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倍,这个题的\(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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */