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 = 100010;
const int mod = 1e9+7;

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*2];  // 注意要开两倍边的空间，加边时以无向图处理，加了双向边

int n, child[maxn];
long long ans;
long long fact[maxn];
void pre()
{
    fact[0] = 1;
    for(int i=1;i<maxn;i++)
        fact[i] = fact[i-1] * i % mod;
}

void init()
{
    cnt = 0;
    memset(head, -1, sizeof(head));
    memset(child, 0, 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] = 1;
    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=1;i<n;i++)
        {
            scanf("%d %d %d", &u, &v, &dis);    
            add(u, v, dis);
            add(v, u, dis);
        }
        
        ans = 0;
        dfs(1, -1);
        printf("%lld
", 2*ans*fact[n-1]%mod);
    
    }
    return 0;
}

// 比赛的时候用的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 = 100010;
const int mod = 1e9+7;
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
", fa, u);
    child[u] = 1;
    int len = G[u].size();
    for(int i=0;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[0] = 1;
    for(int i=1;i<maxn;i++)
    {
        fact[i] = fact[i-1] * i % mod;
//        printf("%d %lld
", i, fact[i]);
    }

    int u, v, d;
    while(~scanf("%d", &n))
    {
        memset(child, 0, sizeof(child));
        for(int i=1;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 = 0;
        dfs(1, -1);
        printf("%lld
", 2*ans*fact[n-1]%mod);

        for(int i=1;i<=n;i++) //G[i].clear(); 
            vector<P>().swap(G[i]);
    }
    return 0;
}

View Code

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