【NOIP2015模拟11.5】JZOJ8月5日提高组T3 旅行

题目

若不存在第\(k\)短路径时，输出“Stupid Mike”

题解

题意

给出一个有\(n\)个点的树

问这\(n\)个点两两之间经过道路为奇数的第\(k\)短的路径长度是多少

路径长度特别定义（见题面）

分析

根据题目

很显然当两个点之间的道路为奇数时

肯定一个点的深度是奇数，另一个是偶数

再看一下路径

一条合法路径长度：\(x-x+x-x+x\)……（不要管数字，只注意符号）

可以发现，开头和结尾都是\(+\)

那么我们可以将每个点按照正负正负的顺序求出到根节点（1）的路径

换句话说，从根节点（1）往每个点走，走到\(x\)节点计算它的长度为\(-dis[fa（父亲）]+len（当前这条边的长度）\)

求出\(dis\)之后

把深度为奇数的\(dis\)放到\(a\)

把深度为偶数的\(dis\)放到\(b\)

然后这个问题就转化成了如何求\(a[i]+b[j]\)的第\(k\)小值

建个小根堆

把所有的\(a[i]+b[1]\)放入堆中

每次取出最小的\(a[i]+b[j]\)

放入\(a[i]+b[j+1]\)

最后答案就是第\(k\)次取出的数

Code

#include<cstdio>

#include<algorithm>

using namespace std;

struct node

{

    long long head,to,val,next;

}a[200005];

struct dui

{

    long long val,idi,idj;

}d[200005];

long long n,k,i,x,y,z,n1,n2,num,tot,ans,ans1,ans2,deep[100005],dis[100005],d1[100005],d2[100005];

void add(long long x,long long y,long long z)

{

    tot++;

    a[tot].to=y;

    a[tot].val=z;

    a[tot].next=a[x].head;

    a[x].head=tot;

}

void dfs(long long now,long long fa)

{

    long long i,x;

    for (i=a[now].head;i;i=a[i].next)

    {

        x=a[i].to;

        if (x==fa) continue;

        deep[x]=deep[now]+1;

        dis[x]=-dis[now]+a[i].val;

        dfs(x,now);

    }

}

void up(long long x)

{

    long long t;

    while (x>1&&d[x>>1].val>d[x].val)

    {

        t=d[x].val;

        d[x].val=d[x>>1].val;

        d[x>>1].val=t;

        t=d[x].idi;

        d[x].idi=d[x>>1].idi;

        d[x>>1].idi=t;

        t=d[x].idj;

        d[x].idj=d[x>>1].idj;

        d[x>>1].idj=t;

        x>>=1;

    }

}

void down(long long x)

{

    long long t,y;

    y=x<<1;

    while ((y<=num&&d[y].val<d[x].val)||(y+1<=num&&d[y+1].val<=d[x].val))

    {

        if (y+1<=num&&d[y].val>d[y+1].val) y++;

        t=d[x].val;

        d[x].val=d[y].val;

        d[y].val=t;

        t=d[x].idi;

        d[x].idi=d[y].idi;

        d[y].idi=t;

        t=d[x].idj;

        d[x].idj=d[y].idj;

        d[y].idj=t;

        x=y;

        y=x<<1;

    }

}

int main()

{

    freopen("travel.in","r",stdin);

    freopen("travel.out","w",stdout);

    scanf("%lld%lld",&n,&k);

    for (i=1;i<n;i++)

    {

        scanf("%lld%lld%lld",&x,&y,&z);

        add(x,y,z);

        add(y,x,z);

    }

    deep[1]=0;

    dis[1]=0;

    dfs(1,0);

    for (i=1;i<=n;i++)

    {

        if (deep[i]%2==1)

        {

            n1++;

            d1[n1]=dis[i];

        }

        else

        {

            n2++;

            d2[n2]=dis[i];

        }

    }

    if (n1*n2<k)

    {

        printf("Stupid Mike\n");

        fclose(stdin);

        fclose(stdout);

        return 0;

    }

    sort(d1+1,d1+n1+1);

    sort(d2+1,d2+n2+1);

    for (i=1;i<=n1;i++)

    {

        num++;

        d[num].val=d1[i]+d2[1];

        d[num].idi=i;

        d[num].idj=1;

        up(num);

    }

    for (i=1;i<k;i++)

    {

        ans1=d[1].idi;

        ans2=d[1].idj;

        d[1].val=d[num].val;

        d[1].idi=d[num].idi;

        d[1].idj=d[num].idj;

        num--;

        down(1);

        if (ans2+1<=n2)

        {

            num++;

            d[num].val=d1[ans1]+d2[ans2+1];

            d[num].idi=ans1;

            d[num].idj=ans2+1;

            up(num);

        }

    }

    printf("%lld\n",d[1].val);

    fclose(stdin);

    fclose(stdout);

    return 0;

}

巴特西

【NOIP2015模拟11.5】JZOJ8月5日提高组T3 旅行

【NOIP2015模拟11.5】JZOJ8月5日提高组T3 旅行

题目

题解

Code

最新文章

热门文章