POJ

题意：一张无向有权图，包括边权和点权，求一点，使得到其他点的点权*边权之和最小
思路：
 1 #pragma comment(linker, "/STACK:1000000000")
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <vector>
 7 #define LL long long
 8 #define INF 0xfffffffffffffff
 9 #define IN freopen("in.txt","r",stdin)
10 #define OUT freopen("out.txt", "w", stdout)
11 #define MAXN 50005
12 using namespace std;
13 
14 struct Edge{
15     int to;
16     LL cost;
17     Edge(int to = 0, LL cost = 0) :to(to), cost(cost){};
18 };
19 Edge G[MAXN << 1];
20 int next[MAXN << 1], head[MAXN << 1];
21 int e;
22 void AddEdge(int from, int to, LL cost){
23     e++;
24     next[e] = head[from];
25     head[from] = e;
26     G[e].to = to;
27     G[e].cost = cost;
28 }
29 LL g[MAXN], f[MAXN], dis[MAXN], a[MAXN];
30 int cnt;
31 LL ans;
32 void dfs(int x, int y){
33     g[x] = 0;
34     dis[x] = 0;
35     for (int i = head[x]; i != 0; i = next[i]){
36         Edge& e = G[i];
37         if (e.to == y) continue;
38         dfs(e.to, x);
39         dis[x] += dis[e.to] + 2LL * e.cost * g[e.to];
40         g[x] += g[e.to];
41     }
42     g[x] += a[x];
43 }
44 void work(int x, int y, LL res){
45     f[x] = res;
46     ans = min(f[x], ans);
47     for (int i = head[x]; i != 0; i = next[i]){
48         Edge& e = G[i];
49         if (e.to == y) continue;
50         work(e.to, x, res + 2LL * e.cost * (cnt - 2LL * g[e.to]));
51     }
52 }
53 int main()
54 {
55     //IN;
56     int T;
57     scanf("%d", &T);
58     int n, m;
59     while (T--){
60         scanf("%d", &n);
61         int x, y;
62         LL z;
63         memset(dis, 0, sizeof(dis));
64         memset(head, 0, sizeof(head));
65         memset(a, 0, sizeof(a));
66         e = 0;
67         for (int i = 1; i < n; i++){
68             scanf("%d%d%I64d", &x, &y, &z);
69             AddEdge(x, y, z);
70             AddEdge(y, x, z);
71         }
72         scanf("%d", &m);
73         cnt = 0;
74         for (int i = 1; i <= m; i++){
75             scanf("%d%d", &x, &y);
76             a[x] = y;
77             cnt += y;
78         }
79         dfs(1, 1);
80         ans = INF;
81         work(1, 1, dis[1]);
82         printf("%I64d
", ans);
83         for (int i = 1; i <= n; i++){
84             if (f[i] != ans) continue;
85             printf("%d ", i);
86         }
87         printf("
");
88 
89     }
90     return 0;
91 }