Hdu5441 2015长春赛区网络赛

朴灿烈づ我的快乐病毒、 2022-08-08 14:43 165阅读 0赞

题目大意：有n个城市，城市之间有m条道路，每条道路用时为t。有q次询问，每次询问在时间T内可以在多少对城市之间走动。注意(a,b)和(b,a)算两种方案。

题目分析：我们可以知道，如果n个城市之间相互联通，那么方案数一共有n\*(n-1)个，所以现在我们要求的就是在T范围内有多少城市相互联通以及有多少组。想到用并查集来做，并查集刚好可以计算出联通分量的个数以及每个连通分量的个数。

假设现在有两个连通分量个数分别为n,m，每个分量之间可以走动的城市对已经计算出来了，现在增加一条路径之后这两个分量连通了，那么增加的城市对有多少种呢。我们可以想到，n和m从互不相干到互相连通，所以增加的城市对数是n\*m，在乘上2。网上有人说是(n+m)\*(n+m-1)-n\*(n-1)-m\*(m-1),因为连通之前两个分量可以走动的城市树分别为n\*(n-1)和m\*(m-1)，连通之后为(n+m)\*(n+m-1),相减就得到上面的结果。其实化简之后可以看到，两种方法是一样的。

有人说，既然我们可以直接计算连通之后的城市对数（利用并查集的得到每个连通分量最后的城市个数n就可以得到结果为n\*(n-1)）,这种想法是正确的但是很浪费时间。这样之后还需要统计连通分量的个数以及每个分量的城市数。相对这题来说，效率不高。

之所以利用增加的方法来计算，因为我们可以将q次询问排序之后第i次询问的时候在T范围内构建并查集，这样在i+1次询问的时候可以直接利用前面以及构建好的并查集并直接向里面添加元素即可。这样效率高很多。

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <iomanip>
    
    using namespace std;
    
    const int maxn = 100005;
    int n,m,q,p[20010];
    int a[20010];   //a[i]表示的是结点i的组号，初始值是
    int s[20010];   //s[i]表示的是结点i所属的组中结点的个数(数的大小)
    
    struct node
    {
        int a , b , time ;
    };
    
    node A[maxn],B[20010];
    
    bool cmp(node x , node y)
    {
        return x.time < y.time ;
    }
    
    int Find(int p)
    {
        while(p!=a[p])
        {
            a[p]=a[a[p]];
            p=a[p];
        }
        return p;
    }
    
    void Union(int p,int q)
    {
        int pRoot=Find(p);
        int qRoot=Find(q);//获得p和q的组号
        if(pRoot==qRoot) return ;
        if(s[pRoot]<s[qRoot])
        {
            a[pRoot]=qRoot;
            s[qRoot]+=s[pRoot];
        }
        else
        {
            a[qRoot]=pRoot;
            s[pRoot]+=s[qRoot];
        }
    }
    
    int main()
    {
        int t ;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d%d",&n,&m,&q) ;
            for(int i = 1 ; i <= n ; i++)
            {
                a[i]=i;s[i]=1;
            }
            for(int i = 0 ; i < m ; i++)
            {
                scanf("%d%d%d",&A[i].a,&A[i].b,&A[i].time);
            }
            sort(A,A+m,cmp) ;
            for(int i = 0 ; i < q ; i++)
            {
                scanf("%d",&B[i].time);
                B[i].a=i;
            }
            sort(B,B+q,cmp) ;
            int ans = 0 , j = 0 ;
            for(int i = 0 ; i < q ; i++)
            {
                while(j < m && A[j].time <= B[i].time)
                {
                    int u = Find(A[j].a);
                    int v = Find(A[j].b);
                    j++ ;
                    //cout<<s[u]<<" "<<s[v]<<endl;
                    if(u==v)continue;   //已经计算过了
                    ans+=2 * s[u] * s[v] ;
                    Union(A[j-1].a,A[j-1].b) ; 
                p[B[i].a]=ans;
            }
            for(int i = 0 ; i < q ; i++)
            {
                printf("%d\n",p[i]);
            }
        }
        return 0;
    }