WOJ 1542 Countries 并查集转化新点+最短路

http://acm.whu.edu.cn/land/problem/detail?problem_id=1542

今天做武大的网赛题，哎，还是不够努力啊，只搞出三个

这个题目一看就是个最短路，但是题目数据量太大，n^2承受不起，而且如果只是个最短路，那题目花这么大力气叙述有些城市可以互相免费干嘛呢

这个是聪哥发现的神奇的细节，题目里说It is guaranteed that there are no more 200 coalitions.暂且把这个称作空域，也就是说最终免费的城市都成了一个块，而不同的块只有不超过200个，聪哥当时是这么分析的，如果真是这样的话，那可以先用并查集把这200个块求出来，再对这些块进行Floyd即可，绝对不会超时

但是我当时还抱有疑问，题目里面也没说最后空域是不超过两百个就是这个意思啊，如果全图没有一条为0的路，我是不是可以认为空域为0个呢，这个题目也没说清楚，到底单个的节点算不算一个空域

不过最后AC的结果说明聪哥还是对的

从理论到实际的AC还是有一些问题的，最主要的就是并查集转化成新的节点，不能在生成并查集的时候就急于转化成新节点，等读完所有边并并查集化后，再通过一个n的扫描把不通的块扫出来，并编号，而且此时还要用一个数组记录好某个点对应的新的并查集块编号。

给新的块编好号之后再走一遍一开始读进来的边，更新块与块之间的最短路长度，建好新的图。接着对这个新图跑一遍Floyd即可。

#include <iostream>

#include <cstdio>

#include <cstring>

#define N 100010

#define INF 1<<30

using namespace std;

int u[N],v[N],w[N],n,m;

int f[N],dir[N];

int mat[][];

void init()

{

    for (int i=;i<=n;i++)

        f[i]=i;

}

int findset(int x)

{

    if (x!=f[x])

        return f[x]=findset(f[x]);

}

int unionset(int a,int b)

{

    int r1=findset(a);

    int r2=findset(b);

    if (r1!=r2)

        f[r2]=r1;

}

void floyd(int sum)

{

    int i,j,k;

    for (int i=;i<sum;i++)

    {

        for (int j=;j<sum;j++)

        {

            for (int k=;k<sum;k++)

            {

                if (mat[j][i]>=INF || mat[i][k]>=INF) continue;

                if (j==k) continue;

                if (mat[j][k]>mat[j][i]+mat[i][k])

                {

                    mat[j][k]=mat[j][i]+mat[i][k];

                }

            }

        }

    }

}

int main()

{

    int a,b,x,y,cnt,q;

    while (scanf("%d",&n))

    {

        if (n==) break;

        init();

        cnt=;

        scanf("%d",&m);

        for (int i=;i<m;i++)

        {

            scanf("%d%d%d",&u[i],&v[i],&w[i]);

            x=findset(u[i]);

            y=findset(v[i]);

            if (w[i]== && x!=y)//在读边的同时进行并查集

              unionset(x,y);

        }

        for (int i=;i<=n;i++)

        {

            if (f[i]==i){

                dir[i]=cnt++;//给新的并查集块编号

            }

        }

        for (int i=;i<=n;i++)

        {

            if (f[i]!=i){

                x=findset(i);//使得原先每个点都找到自己对应的新块的编号，不知道为什么，OJ上不用这个循环也能AC，我觉得这一步应该必要啊，难道是数据弱？

                dir[i]=dir[x];

            }

        }

        for (int i=;i<cnt;i++)

        {

            for (int j=;j<cnt;j++) //初始化新图的节点距离

             if (i==j) mat[i][j]=;

             else mat[i][j]=INF;

        }

        for (int i=;i<m;i++)

        {

            x=findset(u[i]);

            y=findset(v[i]);

            if (x!=y)

            {

                a=dir[x];

                b=dir[y];

                if (w[i]<mat[a][b])

                    mat[a][b]=mat[b][a]=w[i];//重新走一遍之前读进来的边，建好新图。

            }

        }

        floyd(cnt);//对新图跑一遍Floyd

        scanf("%d",&q);

        for (int i=;i<q;i++) //对于每次询问，通过并查集特判一下，然后输出即可

        {

            scanf("%d%d",&a,&b);

            x=findset(a);

            y=findset(b);

            if (x==y) {

                puts("");

                continue;

            }

            x=dir[x];//找到该点对应的块编号，最后输出的应该是块与块之间的最短路，因为块内部是免费的，不存在长度。

            y=dir[y];

            if (mat[x][y]>=INF){

                puts("-1");

                continue;

            }

            printf("%d\n",mat[x][y]);

        }

    }

    return ;

}

巴特西

WOJ 1542 Countries 并查集转化新点+最短路

最新文章

热门文章