既见君子

同济医学生的起落落落落人生记录

BZOJ 3365 路程统计

嗯由于上次邱老师来讲课考了一道点分治,看出来了但不会写,后悔至今,所以就写了一道点分裸题达成今年第一个计划,(居然是一发过还开心了一把)

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=100000+5;
int siz,ecnt,ms[INF],size[INF],k,n,G[INF],s[INF],dis[INF];
bool used[INF];
struct edge{
    int to,next,val;
} e[2*INF];
void add(int x,int y,int val){
    e[++ecnt].to=y;
    e[ecnt].next=G[x];
    e[ecnt].val=val;
    G[x]=ecnt;
}
void pre(){
    int m,x,y,z;
    char w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d %c",&x,&y,&z,&w);
        add(x,y,z);
        add(y,x,z);
    }
    scanf("%d",&k);
}
int get_ans(int x,int D){
    /*printf("%d\n",x);
    for(int i=1;i<=s[0];++i) printf("%d ",s[i]);
    printf("\n");*/
    int l=1,r=1;
    int ans=0;
    sort(s+1,s+s[0]+1);
    while(l<=r&&r<=s[0]){
        int lef=D-s[l];
        while(s[r+1]<=lef&&r+1<=s[0]) r++;
        while(s[r]>lef&&l<r) r--;
        ans+=r-l;
        l++;
    }
    //printf("the answer is:%d\n",ans);
    return ans;
}
int getsize(int x,int last){
    size[x]=1;
    for(int i=G[x];i;i=e[i].next){
        int v=e[i].to;
        if(used[v]||v==last) continue;
        size[x]+=getsize(v,x);
    }
    return size[x];
}
int rooty(int x,int last){
    ms[x]=siz-size[x];
    int ret=x;
    for(int i=G[x];i;i=e[i].next){
        int v=e[i].to;
        if(used[v]||v==last) continue;
        ms[x]=max(ms[x],size[v]);
    }
    for(int i=G[x];i;i=e[i].next){
        int v=e[i].to;
        if(used[v]||v==last) continue;
        int u=rooty(v,x);
        if(ms[u]<ms[ret]) ret=u;
    }
    return ret;
}
void get_dis(int x,int last){
    s[++s[0]]=dis[x];
    for(int i=G[x];i;i=e[i].next){
        int v=e[i].to;
        if(used[v]||v==last) continue;
        dis[v]=dis[x]+e[i].val;
        get_dis(v,x);
    }
}
int cut(int x){
    int ans=0;
    siz=getsize(x,-1);//find the size of this tree
    int rem=rooty(x,-1);//find the root of this tree
    //printf("%d %d %d\n",x,rem,siz);
    dis[rem]=0;
    s[0]=0;
    get_dis(rem,-1);//find the dis of every son of this tree and put them into s
    ans+=get_ans(rem,k);//get all of dis(i)+dis(j)<=k
    used[rem]=true;
    for(int i=G[rem];i;i=e[i].next){//keep away from which are in the same subtree but I counted
        s[0]=0;
        int v=e[i].to;
        if(used[v]) continue;
        dis[v]=e[i].val;
        get_dis(v,-1);
        ans-=get_ans(v,k);
    }
    for(int i=G[rem];i;i=e[i].next){//solve the others
        int v=e[i].to;
        if(used[v]) continue;
        ans+=cut(v);
    }
    return ans;
}
int main(){
    freopen("dis.in","r",stdin);
    freopen("dis.out","w",stdout);
    pre();
    printf("%d\n",cut(1));
    return 0;
}


评论
热度(1)
©既见君子
Powered by LOFTER