- // 昨天打了一场网络赛, 表现特别不好, 当然题目难度确实影响了发挥, 但还是说明自己太菜了, 以后还要多多刷题.
- I - Tree and Permutation http://acm.hdu.edu.cn/showproblem.php?pid=6446
简单说明一下题意, 给出一个 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\n", 2*ans*fact[n-1]%mod);
- }
- return 0;
- }
- // 比赛的时候用的 vector 存邻接矩阵, 搞了半天用 map<pair<int,int>, int > 存 dis(u,v), 交上去一直 TLE, 不明白怎么回事, 昨晚调了半天又一直 ML(Memory Limit)
- // 上网查了一下说是 vector 跟 map 内存没有释放什么的, 反正到现在还没弄明白... 以后还是用链式前向星吧
以后还要多多刷题呀~~~
来源: https://www.cnblogs.com/izcat/p/9536635.html