Tree and Permutation (HDU 6446) 题解

// 昨天打了一场网络赛，表现特别不好，当然题目难度确实影响了发挥，但还是说明自己太菜了，以后还要多多刷题。

2018 CCPC 网络赛 I - Tree and Permutation

简单说明一下题意，给出一个1,2,3...N的排列，显然全部共有N!种排列，每种排列的数字代表树上的一个结点，设Pi是其中第i种排列的相邻数字表示的结点的距离之和，让我们求sum(Pi)(1<=i<=N!)。

可以设dis(i, j)为树上任意两点间的最短距离，稍加分析一下容易得到所求答案为 (N-1)! * sum(dis(i, j))。对于dis(i, j)很容易想到用Floyd算法来求，但题目数据量为1e5很明显复杂度O(n^3)的算法肯定超时。由于这是一棵树，dis(i, j)的最短路径是唯一的（不存在环），那么对于相邻结点u, v，可以发现边(u, v)走过的次数为左边结点数量*右边结点数量。现在大概就是一道树形dp的题了，剩下的就是代码实现了。AC代码如下：

#include <cstdio>

#include <cstring>

using namespace std;

const int maxn = ;

const int mod = 1e9+;

int head[maxn], cnt;

struct Edge{

    int to, nxt, w;

    Edge(){}

    Edge(int _to, int _nxt, int _w): to(_to), nxt(_nxt), w(_w){}

};

Edge edge[maxn*];  // 注意要开两倍边的空间，加边时以无向图处理，加了双向边

int n, child[maxn];

long long ans;

long long fact[maxn];

void pre()

{

    fact[] = ;

    for(int i=;i<maxn;i++)

        fact[i] = fact[i-] * i % mod;

}

void init()

{

    cnt = ;

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

    memset(child, , sizeof(child));

}

void add(int from, int to, int weight)

{

    edge[cnt] = Edge(to, head[from], weight);

    head[from] = cnt++;

}

void dfs(int u, int fa)

{

    child[u] = ;

    for(int i=head[u];~i;i=edge[i].nxt)

    {

        int v = edge[i].to;

        if(v!=fa)

        {

            dfs(v, u);

            child[u] += child[v];

            ans += (long long)child[v]*(n-child[v])*edge[i].w%mod; // 没有强制转换相乘会溢出，WA WA大哭。。。

            if(ans>mod) ans -= mod;

        }

    }

}

int main()

{

    pre();

    int u, v, dis;

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

    {

        init();

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

        {

            scanf("%d %d %d", &u, &v, &dis);

            add(u, v, dis);

            add(v, u, dis);

        }

        ans = ;

        dfs(, -);

        printf("%lld\n", *ans*fact[n-]%mod);

    }

    return ;

}

// 比赛的时候用的vector存邻接链表，瞎搞了半天用map<pair<int,int>, int>存dis(u,v)，交上去一直TLE，不明白怎么回事，昨晚调了半天又一直ML(Memory Limit)

// 上网查了一下说是vector跟map内存没有释放什么的，反正到现在还没弄明白。。。以后还是用链式前向星吧

update补充：

经过不懈探索，用邻接链表实现了AC。舍弃了map存树上的边的方法，将结点与边放到pair构成的vetor里

typedef pair<int, int> P; // first 为结点，second为边

vector<P> G[maxn]; // G[u]存相邻结点的信息：G[u][i].second 为u到结点G[u][i].first的边

这种写法应该不常见，以后还是要尽量避免使用vector。至于释放vector的内存（不只是清空），我尝试了以下三种操作都可以AC，不确定孰优孰劣。以后学习C++再好好研究一番。

memset(G, 0, sizeof(G));
for(int i=1;i<=n;i++) G[i].clear();
for(int i=1;i<=n;i++) vector<P>().swap(G[i]);

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

#include <map>

using namespace std;

const int maxn = ;

const int mod = 1e9+;

typedef long long ll;

typedef pair<int, int> P;

vector<P> G[maxn];

ll fact[maxn], ans;

int n, child[maxn]; 

void dfs(int u, int fa)

{

//    printf("%d->%d\n", fa, u);

    child[u] = ;

    int len = G[u].size();

    for(int i=;i<len;i++)

    {

        int v = G[u][i].first;

        if(v!=fa)

        {

            dfs(v, u);

            child[u] += child[v];

            ans += (long long)child[v]*(n-child[v])*G[u][i].second % mod;

            ans %= mod;

        }

    }

}

int main()

{

    fact[] = ;

    for(int i=;i<maxn;i++)

    {

        fact[i] = fact[i-] * i % mod;

//        printf("%d %lld\n", i, fact[i]);

    }

    int u, v, d;

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

    {

        memset(child, , sizeof(child));

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

        {

            scanf("%d %d %d", &u, &v, &d);

            G[u].push_back(P(v, d));

            G[v].push_back(P(u, d));

        }

        ans = ;

        dfs(, -);

        printf("%lld\n", *ans*fact[n-]%mod);

        for(int i=;i<=n;i++) //G[i].clear();

            vector<P>().swap(G[i]);

    }

    return ;

}

以后还要多多刷题呀~~~

巴特西

Tree and Permutation (HDU 6446) 题解

2018 CCPC 网络赛 I - Tree and Permutation

最新文章

热门文章