做广告：

#include <stdio.h>

int main()

{

    puts("转载请注明出处[vmurder]谢谢");

    puts("网址：blog.csdn.net/vmurder/article/details/44308173");

}

题意：

求是否有长度为K的路径。

每组数据

N，表示树有N个点。

然后N行，每行若干个数对(a,b)，当中第i行时表示i到a有一条长为b的无向边。输入到0截止。

然后若干个数表示K，每一个数输出下。

到0为止。

然后数据的N也是到0为止。

存在 puts("AYE");

否则 puts("NAY");

每组数据最后输出一个dot，就是 .

题解：

三倍经验题，

POJ1987

http://blog.csdn.net/vmurder/article/details/44307489

POJ1741

http://blog.csdn.net/vmurder/article/details/44302921

代码：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 10100

#define inf 0x3f3f3f3f

using namespace std;

int n,m;

struct Eli

{

    int v,len,next;

}e[N<<1];

int head[N],cnt;

bool rem[N];

inline void add(int u,int v,int len)

{

    e[++cnt].v=v;

    e[cnt].len=len;

    e[cnt].next=head[u];

    head[u]=cnt;

}

int f[N],f2[N],son[N];

int TreeCenter,length;

int dfs1(int x,int p)

{

    int i,v;

    f[x]=f2[x]=0;

    for(i=head[x];i;i=e[i].next)

    {

        v=e[i].v;

        if(v==p||rem[v])continue;

        int temp=dfs1(v,x);

        if(temp>f[x])

        {

            f2[x]=f[x];

            f[x]=temp;

            son[x]=v;

        }

        else if(temp>f2[x])

            f2[x]=temp;

    }

    return f[x]+1;

}

int g[N];

void dfs2(int x,int p)

{

    int i,v;

    if(max(f[x],g[x])<length)

    {

        length=max(f[x],g[x]);

        TreeCenter=x;

    }

    for(i=head[x];i;i=e[i].next)

    {

        v=e[i].v;

        if(v==p||rem[v])continue;

        if(v==son[x])g[v]=max(g[x],f2[x])+1;

        else g[v]=max(g[x],f[x])+1;

        dfs2(v,x);

    }

    return ;

}

inline int get_TreeCenter(int x)

{

    if(rem[x])return 0;

    length=inf,g[x]=0;

    dfs1(x,0),dfs2(x,0);

    return TreeCenter;

}

struct Summorer

{

    int a,b;

    // 权值，子树标号

    Summorer(int _a=0,int _b=0):a(_a),b(_b){}

}src[N];

inline int cmp(Summorer a,Summorer b)

{

    return a.a<b.a;

}

int size[N];

void dfs3(int x,int p,int t,int len)

{

    src[++cnt]=Summorer(len,t);

    size[x]=1;

    int i,v;

    for(i=head[x];i;i=e[i].next)

    {

        v=e[i].v;

        if(rem[v]||v==p)continue;

        dfs3(v,x,t,len+e[i].len);

        size[x]+=size[v];

    }

    return ;

}

bool work(int x,int n)

{

    if(!n)return 0;

    rem[x=get_TreeCenter(x)]=1;

    int num=0,i,j,k,v,p;

    cnt=0;

    for(i=head[x];i;i=e[i].next)

    {

        v=e[i].v;

        if(rem[v])continue;

        dfs3(v,x,++num,e[i].len);

    }

    sort(src+1,src+cnt+1,cmp);

    for(p=n,i=0;i<=n;i++)

    {

        while(i<p&&src[i].a+src[p].a>m)p--;

        if(i>=p)break;

        for(j=p;j>i&&src[i].a+src[j].a==m;j--)

            if(src[i].b!=src[j].b)return 1;

        if(src[i+1].a!=src[i].a)p=j;

    }

    for(i=head[x];i;i=e[i].next)

    {

        v=e[i].v;

        if(rem[v])continue;

        if(work(v,size[v]-1))return 1;

    }

    return 0;

}

int main()

{

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

    int i,a,b,c;

    while(scanf("%d",&n),n)

    {

        cnt=0;

        memset(head,0,sizeof head);

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

        {

            while(scanf("%d",&a),a)

            {

                scanf("%d",&b);

                add(i,a,b),add(a,i,b);

            }

        }

        while(scanf("%d",&m),m)

        {

            memset(rem,0,sizeof rem);

            if(work(1,n-1))puts("AYE");

            else puts("NAY");

        }

        puts(".");

    }

    return 0;

}

版权声明：本文博主原创文章，博客，未经同意不得转载。