HDU 4750 Count The Pairs(最小生成树)

HDU 4750 Count The Pairs(最小生成树)

http://acm.hdu.edu.cn/showproblem.php?pid=4750

题意:

有一个N个顶点M条边(边长各不相同)的无向图,现在有Q个询问,对于每个询问有1个数c, 要你输出任意两点的所有路上的最大边的最小值(其实就是最小生成树上的瓶颈路)>=c的这些点对的个数.

分析:

其实本题的本质就是关于最小生成树上任意两点a与b之间的瓶颈路长. 上述的a到b的所有路上的最大边的最小值其实就是整个图的最小生成树上a到b的唯一路径上的最长边,即a到b的瓶颈边上.

如果我们知道了任意两点a与b之间的瓶颈边长,那么我们就能统计出对应的结果,但是这种预处理的方式会超时且超内存.

还记不记得图中两点a与b的瓶颈边长怎么求?把所有边按边长从小到大排序,然后依次添加边到图中去,如果当添加了一条长为x的边后,a和b连通了,那么a与b的瓶颈边长就是x.(想想是不是)

在延伸一下,当添加完x边后,不仅仅是a与b连通了,a所属连通分量的所有点都与b所属分量的所有点连通了,所以瓶颈边长为x的点对数= a分量的点数* b分量的点数*2(乘以2是因为(a,b)和(b,a)是不同的点对. 其实这句话是有问题的,因为边长为x的边可能不止1条,但是在本题的条件下,各边的权值都不同,所以是没问题的.)

从上面那步我们已经知道了对于特定长度x,瓶颈边长==x的点对数目了. 现在我们对于询问q来说,我们需要找到瓶颈边长>=q的点对数为多少个? 我们只需要求出对应的x>=q的点对总数sum即可.(这里可以用二分查找或lower_bound或树状数组都行).本题可以不用离线处理.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int maxn= 10000+10;
const int maxm=500000+10;

struct Edge
{
    int u,v,dist;
    Edge(){}
    Edge(int u,int v,int dist):u(u),v(v),dist(dist){}
    bool operator<(const Edge&rhs)const
    {
        return dist<rhs.dist;
    }
};


struct Kruskal
{
    int n,m;
    Edge edges[maxm];
    int fa[maxn];
    int sum[maxn];//并查集的点数目
    int findset(int x){ return fa[x]==-1?x:fa[x]=findset(fa[x]); }

    vector<int> edge_len;//保存从小到大的瓶颈边长
    int s[maxm];//保存从小到大瓶颈边长对应的(a,b)点对数目,
                //s[i]=10表长edge_len[i]的瓶颈边对应10个点对

    void init(int n)
    {
        this->n=n;
        m=0;
        memset(fa,-1,sizeof(fa));
        for(int i=0;i<=n;i++) sum[i]=1;
        edge_len.clear();
        memset(s,0,sizeof(s));
    }

    void AddEdge(int u,int v,int dist)
    {
        edges[m++]=Edge(u,v,dist);
    }

    void kruskal()
    {
        int cnt=0;
        sort(edges,edges+m);

        for(int i=0;i<m;i++)
        {
            int u=edges[i].u, v=edges[i].v;
            if(findset(u) != findset(v))
            {
                edge_len.push_back(edges[i].dist);
                s[cnt] = sum[findset(v)]*sum[findset(u)]*2;

                sum[findset(v)] += sum[findset(u)]; //注意顺序
                fa[findset(u)] = findset(v);        //注意顺序
                if(++cnt>=n-1) break;
            }
        }

        for(int i=1;i<cnt;i++)//累加点对和
            s[i] +=s[i-1];
        int Q;
        scanf("%d",&Q);
        while(Q--)
        {
            int x; scanf("%d",&x);
            int index = lower_bound(edge_len.begin(), edge_len.end(), x)-edge_len.begin();//寻找下确界
            int ans;
            if(index>0) ans = s[cnt-1]-s[index-1];//下确界为0时需要特殊处理
            else ans=s[cnt-1];
            printf("%d\n",ans);
        }
    }
}KK;

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        KK.init(n);
        for(int i=0;i<m;i++)
        {
            int u,v,d;
            scanf("%d%d%d",&u,&v,&d);
            KK.AddEdge(u,v,d);
        }
        KK.kruskal();
    }
    return 0;
}