Problem Description
Chinese Postman Problem is a very famous hard problem in graph theory. The problem is to find a shortest closed path or circuit that visits every edge of a (connected) undirected graph. When the graph has an Eulerian Circuit (a closed walk that covers every
edge once), that circuit is an optimal solution.
This problem is another version of Postman Problem. Assume there are n towns and n-1 roads, and there is a unique path between every pair of towns. There are n-1 postmen in every town, and each postman in one town regularly sends mails to one of the other
n-1 towns respectively. Now, given the length of each road, you are asked to calculate the total length that all the postmen need to travel in order to send out the mails.
For example, there are six towns in the following picture. The 30 postmen should totally travel 56. The postmen in town 0 should travel 1, 2, 2, 2, 3 respectively, the postmen in town 1 should travel 1, 1, 1, 1, 2 respectively, the postmen in town 2 should
travel 1, 1, 2, 2, 2 respectively, the postmen in town 3 should travel 1, 2, 3, 3, 3 respectively, the postmen in town 4 should travel 1, 2, 2, 2, 3 respectively, and the postmen in town 5 should travel 1, 2, 2, 2, 3 respectively. So the total distance is
56.
Input
The first line of the input contains an integer T(T≤20), indicating the number of test cases. Each case begins with one integer n(n≤100,000), the number of towns. In one case, each of the following n-1 lines describes the length of path between pair a and
b, with the format a, b, c(1≤c≤1000), indicating that town a and town b are directly connected by a road of length c. Note that all the n towns are numbered from 0 to n-1.
Output
For each test case, print a line containing the test case number (beginning with 1) and the total sum of the length that all postmen should travel.
Sample Input
160 1 11 2 12 3 11 4 11 5 1
Sample Output
Case 1: 56
Source
2011年全国大学生程序设计邀请赛(福州)
题意:给定一个n-1边,n个点的图,点都是连通的,求所有点到其他点的距离之和。
思路:问题转换为,每条边要走几次,距离为所有边权值*次数之和,对于每条边走几次,就看如果去除这条边,那么分成的两个图中点数之积(想想为什么)。这样一来只要进行一次dfs即可。
代码:
#include <stdio.h>
#include <string.h>
const int N = 200005;
typedef long long ll;
int t, n, first[N], next[N], u[N], v[N], E, vis[N];
ll w[N], time[N];
void add(int a, int b, int value) {
u[E] = a; v[E] = b; w[E] = value; time[E] = 0;
next[E] = first[u[E]]; first[u[E]] = E;
E ++;
}
void init() {
int a, b, value;
memset(vis, 0, sizeof(vis));
E = 0; memset(first, -1, sizeof(first));
scanf("%d", &n);
for (int i = 0; i < n - 1; i ++) {
scanf("%d%d%d", &a, &b, &value);
add(a, b, value);
add(b, a, value);
}
}
ll dfs(int u) {
ll t = 0;
vis[u] = 1;
for (int e = first[u]; e != -1; e = next[e]) {
if (vis[v[e]]) continue;
ll cnt = dfs(v[e]);
t += cnt;
time[e] = time[e^1] = cnt * (n - cnt);
}
return t + 1;
}
void solve() {
ll ans = 0;
dfs(0);
for (int i = 0; i < E; i ++) {
ans += time[i] * w[i];
}
printf("%lld\n", ans);
}
int main() {
int cas = 0;
scanf("%d", &t);
while (t--) {
init();
printf("Case %d: ", ++cas);
solve();
}
return 0;
}
分享到:
相关推荐
求最大乘积 的源代码 次题是fzu 4月月赛题 是一道数学题啊
fzu online judge 的几道题,我的解题过程与思路,虽然都是很easy的题目,不过,重在参与嘛,哈哈
2021FZU计算机视觉作业(九)
2021FZU计算机视觉作业(七)
2021FZU计算机视觉作业(八)
2021FZU计算机视觉期末复习
不要下载此版的,请下载最新的http://download.csdn.net/source/1664620 离线版的福大acm在线评测OJ系统题目 更新到2009年8月 (注:chm电子书格式化)
fzu大数据基础实验4
C#miniword完整版,FZU作业,MINIWORD
FZU软件工程web课程复习资料-整理
FZU2021计算机视觉慕课答案(一)
FZU软件工程操作系统课程复习资料-整理
这是关于我们飞跃手册项目的相关文档,包括成员分组信息表格,各组成员任务概要文档,项目日记等文档。 (This is a collection of documents relating to our Leapfrog Handbook project, including member ...
FZU2021计算机视觉答案(三)
FZU2021计算机视觉答案(四)
2021FZU计算机视觉答案(五)
2021FZU计算机视觉答案(二 )
2021FZU计算机视觉答案(六)
2011 ACM 多校联合 2011 MU11 13 FZU
ACM数学_FZU...............绝密..........