A simple Blog for wyx I've been down the bottle hoping.
3522: [Poi2014]Hotel 树形dp
发表于: | 分类: Oi | 评论:0 | 阅读:238

题目大意
给定一棵树,找到三个点,使得三个点到中心点的距离相同,中心点相同算相同方案,求一共多少种方案
树的节点数 $<=5000$
大概这题的数据范围比较小……我就暴力过的……
我要是知道正解以后再重写一下
先说一下暴力怎么写吧

枚举中间点,记录总数,两个点的合法组合数(即不在同一棵子树中的任意搭配)
然后每次$BFS$或者$DFS$跑一下开桶统计一下就行了

时间复杂度$O(N^2)$
要是觉得虚你可以写一下非递归,能快一些

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
#define N 5000+5
#define M 10000+5
typedef long long LL;
int head[N];

struct graph
{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x);
    head[y] = cnt;
}

int tmp[N],f[N],g[N];

void DFS(int x,int fa,int depth)
{
    tmp[depth]++;
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
            DFS(edge[i].to,x,depth+1);
}

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main()
{
    int n = read();
    for(int i=1;i<n;++i)
    {
        int x = read(),y =read();
        add(x,y);
    }
    LL ans = 0;
    for(int i=1;i<n;++i)
    {
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);
        for(int j=head[i];j;j=edge[j].next)
        {
            memset(tmp,0,sizeof tmp);
            DFS(edge[j].to,i,1);
            for(int k=1;k<=n;++k)
            {
                ans += (LL)(g[k])*tmp[k];
                g[k] +=(LL)f[k] * tmp[k];
                f[k] += tmp[k];
            }
        }
    }
    cout<<ans<<endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP