poj 2114 树的分治可作模板

/*

啊啊啊啊啊啊啊本题证明一个问题，在实际应用中sort比qsort块

还有memset这类初始化能不加尽量别加，很浪费时间

原来的程序把qsort该成sort，去掉一个无用memset就a了时间不到一半

题意：和poj1741差不多，不过本题求的是dis[i]+dis[j]==dis[k];

*/

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<algorithm>

using namespace std;

#define N  11000

#define inf 0x3fffffff

struct node {

int u,v,w,next;

}bian[N*4];

int yong,head[N];

void init() {

 yong=0;

 memset(head,-1,sizeof(head));

}

void addedge(int u,int v,int w) {

bian[yong].u=u;

bian[yong].v=v;

bian[yong].w=w;

bian[yong].next=head[u];

head[u]=yong++;

}

int minn,ma,vis[N],diss[N],len,num[N],nn;

void  dfs1(int u,int fa) {

   int i;

   nn++;

   for(i=head[u];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(v!=fa&&!vis[v])

    dfs1(v,u);

   }

   return ;

}

int Max(int v,int vv) {

return v>vv?v:vv;

}

void dfs2(int u,int fa) {

  num[u]=1;

  int i,tit=0;

  for(i=head[u];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(v!=fa&&!vis[v]) {

        dfs2(v,u);

        num[u]+=num[v];

        tit=Max(tit,num[v]);

    }

  }

   tit=Max(tit,nn-num[u]);

   if(tit<minn) {

    minn=tit;

    ma=u;

   }

   return ;

}

void dfs4(int u,int fa,int w) {

 int i;

 diss[len++]=w;

 for(i=head[u];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(v!=fa&&!vis[v])

        dfs4(v,u,w+bian[i].w);

 }

 return ;

}

int m;

int dfs3(int u,int fa,int w) {

   len=0;

   dfs4(u,fa,w);

 sort(diss,diss+len);

    int i,j,ans=0,k;

    for(i=0,j=len-1;i<j;i++) {//1000ms

        while(i<j&&diss[i]+diss[j]>m)

            j--;

            k=j;

        while(i<k&&diss[i]+diss[k]==m) {

                k--;

                ans++;

        }

    }

    /*

     i=0;j=len-1;

    while(i<j) {//688ms

        if(diss[i]+diss[j]<m)

            i++;

        else

            if(diss[i]+diss[j]>m)

                j--;

        else {

            if(diss[i]==diss[j]) {

                ans+=(j-i+1)*(j-i)/2;

                break;

            }

           ki=i;kj=j;

            while(diss[i]==diss[ki])ki++;

            while(diss[j]==diss[kj])kj--;

            ans+=(ki-i)*(j-kj);

            i=ki;j=kj;

        }

    }

    */

    return ans;

}

int dfs(int u) {

   minn=inf;

   nn=0;

   dfs1(u,-1);

   dfs2(u,-1);

   int ans=dfs3(ma,-1,0);

 //  printf("%d\n",ma);

   vis[ma]=1;

   int i;

   for(i=head[ma];i!=-1;i=bian[i].next) {

    int v=bian[i].v;

    if(!vis[v]) {

        ans-=dfs3(v,-1,bian[i].w);

        ans+=dfs(v);

    }

   }

   return ans;

}

int main() {

   int  n,i,j,k;

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

        init();

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

    while(scanf("%d",&j),j) {

            scanf("%d",&k);

            addedge(i,j,k);

    addedge(j,i,k);

        }

    }

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

       memset(vis,0,sizeof(vis));

       k=dfs(1);

       if(k)

        printf("AYE\n");

        else

            printf("NAY\n");

    }

    printf(".\n");

   }

return 0;

}
巴特西

poj 2114 树的分治可作模板

最新文章

热门文章

巴特西

poj 2114 树的分治 可作模板

最新文章

热门文章

poj 2114 树的分治可作模板
