洛谷 U32911 道路维护解题报告

U32911 道路维护

题目背景

最近很多人投诉说C国的道路破损程度太大，以至于无法通行。

C国的政府很重视这件事，但是最近财政有点紧，不可能将所有的道路都进行维护，所以他们决定按照下述方案进行维护。

题目描述

将C国抽象成一个无向图，定义两个城市之间的某条路径的破损程度为该条路径上所有边破损程度的最大值，定义两个城市之间的破损程度为两个城市之间所有路径破损程度的最小值。

C国政府向你提问多次，有多少个城市对的破损程度不超过(L)，他们将依照你的回答来决定到底怎样维护C国的道路

输入格式

第一行三个数(n,m,q)，表示图的点数和边数以及政府的询问数

以下(m)行每行三个数(a,b,c)，表示一条连接(a,b)且破损程度为(c)的无向边

接下来一行(q)个数(L_i)，表示询问有多少个城市对的破损程度不超过(L_i)

输出格式

一行(q)个数，对应每个询问，输出满足要求的城市对的数目。

说明

一个城市对((i,j))，满足(i<j)，也就是说((i,j))，((j,i))只算一次，且两个城市不同

数据范围

测试点编号	(n)	(m)	(q)
1	50	100	100
2	200	400	100
3	300	500	1000
4	1000	10000	10000
5	5000	20000	10000
6	5000	20000	100000
7	10000	50000	100000
8	10000	50000	100000
9	20000	100000	100000
10	20000	100000	100000

所有的(L_i)满足(L_ile 10^9)

一眼上去可以最小生成树+点剖

但想一下我们发现其实是可以离线的

把询问和边权放在一起排序，模拟krus建最小生成树过程，全局更新答案

Code:

#include <cstdio>
#include <algorithm>
const int N=20010;
const int M=200010;
struct node
{
    int u,v,w,id;
    bool friend operator <(node n1,node n2)
    {
        if(n1.w==n2.w) return n1.id<n2.id;
        return n1.w<n2.w;
    }
}e[M];
int f[N],siz[N],ans[M>>1],sum,n,m,q;
int Find(int x)
{
    return f[x]=f[x]==x?x:Find(f[x]);
}
int cal(int x)
{
    return x*(x-1)/2;
}
void Merge(int x,int y)
{
    int X=Find(x),Y=Find(y);
    sum-=cal(siz[X])+cal(siz[Y]);
    siz[X]+=siz[Y];
    sum+=cal(siz[X]);
    f[Y]=Find(X);
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        f[i]=i,siz[i]=1;
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&e[i+m].w);
        e[i+m].id=i;
    }
    std::sort(e+1,e+1+m+q);
    for(int i=1;i<=m+q;i++)
    {
        if(!e[i].id&&Find(e[i].u)!=Find(e[i].v))
            Merge(e[i].u,e[i].v);
        if(e[i].id)
            ans[e[i].id]=sum;
    }
    for(int i=1;i<=q;i++)
        printf("%d ",ans[i]);
    return 0;
}

2018.7.26**

洛谷 U32911 道路维护 解题报告