首页 > 代码库 > tyvj-1460 旅行

tyvj-1460 旅行

题目描写叙述:

A国有n座城市,每座城市都十分美,这使得A国的民众们很喜欢旅行。

然而,A国的交通十分落后,这里仅仅有m条双向的道路。而且这些道路都十分崎岖,有的甚至还是山路。仅仅能靠步行。通过每条道路的长度、泥泞程度等因素,我们给每条道路评估一个“崎岖度”,表示通过这条道路的不舒适程度。
从X城市经过若干条道路到达Y城市,我们称这次旅行的“代价”为所经过道路“崎岖度”的最大值。当然。假设从X城市到Y城市有多条路线。民众们会自觉选择“代价”最小的路线进行旅行。可是,A国的民众也是有脾气的。假设旅行的“代价”超过了他们的“忍耐度”,他们就不选择这个旅行了。甚至宁愿在家里宅着。


如今A国的国王想进行若干次询问:给定民众的“忍耐度”。问还有多少对城市(X,Y)会存在旅行?请你对国王的每次询问分别给出回答。


n<=100000,m<=200000,Q<=200000。其它数不超过10^9。


题解:

对于随意两点之间来说。起作用的仅仅有崎岖度最小的的那条链上的最长边。

所以考虑维护这种边与图的关系;

对边从小到大排序,然后维护一个连通性的并查集。

那么假设令f[i]为忍耐度为第i小的边时的答案的话;

能够得到转移方程f[i]=f[i-1]-size[x]*(size[x]-1)/2-size[y]*(size[y]-1)/2+(size[x]+size[y])*(size[x]+size[y]-1)/2;

size[x]表示x所在连通块中的点数。

然后为了高速的处理询问。能够做一些预处理;

使边权和f数组下标相相应。这样就能够通过二分边权数组来得到答案;

时间复杂度O(mlogm+Qlogm);


代码:


#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 110000
using namespace std;
typedef long long ll;
struct node
{
    int x,y,val;
}a[N<<1];
int f[N],len[N<<1];
ll ans[N<<1],size[N];
int find(int x)
{
    if(f[x]==x)
        return x;
    f[x]=find(f[x]);
    size[f[x]]+=size[x];
    size[x]=0;
    return f[x];
}
ll mul(ll x)
{
    return x*(x-1)/2;
}
int cmp(node a,node b)
{
    return a.val<b.val;
}
int main()
{
    int n,m,q,i,j,k,x,y,fx,fy;
    scanf("%d%d%d",&n,&m,&q);
    for(i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val);
    for(i=1;i<=n;i++)
        f[i]=i,size[i]=1;
    sort(a+1,a+1+m,cmp);
    for(i=1;i<=m;i++)
    {
        x=a[i].x,y=a[i].y;
        len[i]=a[i].val;
        fx=find(x),fy=find(y);
        if(fx!=fy)
        {
            ans[i]=ans[i-1]-mul(size[fy])-mul(size[fx])+mul(size[fx]+size[fy]);
            f[fx]=fy;
            size[fy]+=size[fx];
            size[fx]=0;
        }
        else
            ans[i]=ans[i-1];
    }
    for(i=1;i<=q;i++)
    {
        scanf("%d",&k);
        printf("%lld\n",ans[upper_bound(len+1,len+1+m,k)-len-1]);
    }
    return 0;
}



tyvj-1460 旅行