Accumulation Degree
| Time Limit: 5000MS |
|
Memory Limit: 65536K |
| Total Submissions: 248 |
|
Accepted: 30 |
Description
Trees
are an important component of the natural landscape because of their
prevention of erosion and the provision of a specific ather-sheltered
ecosystem in and under their foliage. Trees have also been found to
play an important role in producing oxygen and reducing carbon dioxide
in the atmosphere, as well as moderating ground temperatures. They are
also significant elements in landscaping and agriculture, both for
their aesthetic appeal and their orchard crops (such as apples). Wood
from trees is a common building material.
Trees also play an
intimate role in many of the world's mythologies. Many scholars are
interested in finding peculiar properties about trees, such as the
center of a tree, tree counting, tree coloring. A(x) is one of such properties.
A(x) (accumulation degree of node x) is defined as follows:
- Each edge of the tree has an positive capacity.
- The nodes with degree of one in the tree are named terminals.
- The flow of each edge can't exceed its capacity.
- A(x) is the maximal flow that node x can flow to other terminal nodes.
Since it may be hard to understand the definition, an example is showed below:
| A(1)=11+5+8=24 |
| Details: |
1->2 |
11 |
| |
1->4->3 |
5 |
| |
1->4->5 |
8(since 1->4 has capacity of 13) |
| A(2)=5+6=11 |
| Details: |
2->1->4->3 |
5 |
| |
2->1->4->5 |
6 |
| A(3)=5 |
| Details: |
3->4->5 |
5 |
| A(4)=11+5+10=26 |
| Details: |
4->1->2 |
11 |
| |
4->3 |
5 |
| |
4->5 |
10 |
| A(5)=10 |
| Details: |
5->4->1->2 |
10 |
The
accumulation degree of a tree is the maximal accumulation degree among
its nodes. Here your task is to find the accumulation degree of the
given trees.
Input
The first line of the input is an integer T which indicates the number of test cases. The first line of each test case is a positive integer n. Each of the following n - 1 lines contains three integers x, y, z separated by spaces, representing there is an edge between node x and node y, and the capacity of the edge is z. Nodes are numbered from 1 to n.
All the elements are nonnegative integers no more than 200000. You may assume that the test data are all tree metrics.
Output
For each test case, output the result on a single line.
Sample Input
1
5
1 2 11
1 4 13
3 4 5
4 5 10
Sample Output
26
Source
這道題的基本思想是樹(shù)形DP，如果不能理解的話請(qǐng)?jiān)噲D把雙向邊看成兩個(gè)單向邊，再比劃比劃就出來(lái)了。
當(dāng)然不一定非要以邊做為DP的單元，也可以歸到邊上（如果你有那份心的話）。
比賽的時(shí)候因?yàn)閿?shù)據(jù)量大而Stack Overflow，一直想寫(xiě)人工模擬棧，但因?yàn)闆](méi)寫(xiě)過(guò)，在比賽中寫(xiě)不出來(lái)。
五一節(jié)虛心的跟alpc62學(xué)習(xí)了怎么寫(xiě)人工模擬棧，核心思想就是將同一個(gè)DFS內(nèi)的不同DFS做個(gè)標(biāo)記，這樣在出棧的時(shí)候就可以判斷自己所處的位置，也就知道自己該采取什么行動(dòng)了。
比如
void DFS(int x) {
for(int i = 0; i < head[x].size(); ++i) {
DFS(head[x][i]);
}
}
如果把(x, i)這個(gè)2元組壓入棧也就知道自己現(xiàn)在所處的地方了。
如果有更多的內(nèi)部DFS，同樣是加對(duì)應(yīng)的標(biāo)記。
當(dāng)然，BFS也是一種很好的選擇（應(yīng)該說(shuō)大多數(shù)隊(duì)伍會(huì)選擇BFS而不是人工模擬棧）
//Accumulation Degree in BFS
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define Min(a, b) (a<b?a:b)
#define Max(a, b) (a>b?a:b)
struct Node
{
int x, i, pre;
Node() {}
Node(int xx, int ii, int pp) {x=xx, i = ii, pre=pp;}
};
struct Edge
{
int x, w, dp;
Edge() {}
Edge(int xx, int ww, int dd=0) { x=xx,w=ww,dp=dd;}
};
const int N = 200010;
vector<Edge> e[N];
bool chk[N];
int n, flow[N];
void solve() {
int i, j, k;
vector<Node> Q;
fill(chk, chk + n, 0);
fill(flow, flow + n, 0);
for(i = 0; i < n && e[i].size()!=1; ++i);
int st = 0, end = 0;
chk[i] = 1;
for(j = 0; j < e[i].size(); ++j) {
Q.push_back(Node(i, j, -1));
end++;
chk[e[i][j].x] = 1;
}
while(st < end) {
int x = e[Q[st].x][Q[st].i].x, pre = Q[st].pre;
for(i = 0; i < e[x].size(); ++i) {
if(!chk[e[x][i].x]) {
Q.push_back(Node(x, i, st));
end++;
chk[e[x][i].x] = 1;
}
}
++st;
}
for(i = end-1; i >= 0; --i) {
int x = Q[i].x, pre = Q[i].pre, idx = Q[i].i;
if(e[e[x][idx].x].size() == 1) e[x][idx].dp = e[x][idx].w;
else e[x][idx].dp = Min(e[x][idx].dp, e[x][idx].w);
if(pre == -1) continue;
int prex = Q[pre].x, preidx = Q[pre].i;
e[prex][preidx].dp += e[x][idx].dp;
}
for(i = 0; i < e[Q[0].x].size(); ++i) {
flow[Q[0].x] += e[Q[0].x][i].dp;
}
for(i = 0; i < end; ++i) {
int x = Q[i].x, pre = Q[i].pre, idx = Q[i].i;
int y = e[x][idx].x, xx;
for(xx = 0; xx < e[y].size() && e[y][xx].x != x; ++xx);
if(pre == -1) {
e[y][xx].dp = e[y][xx].w;
}
else {
e[y][xx].dp = Min(e[y][xx].dp, e[y][xx].w);
}
for(j = 0; j < e[y].size(); ++j) {
flow[y] += e[y][j].dp;
}
for(j = 0; j < e[y].size(); ++j) {
int yy = e[y][j].x;
if(yy == x) continue;
for(k = 0; k < e[yy].size() && e[yy][k].x != y; ++k);
e[yy][k].dp = flow[y] - e[y][j].dp;
}
}
int max = 0;
for(i = 0; i < n; ++i)
max = Max(max, flow[i]);
printf("%d\n", max);
}
int main() {
int ntc;
int i;
int x, y, w;
scanf("%d", &ntc);
while(ntc--) {
scanf("%d", &n);
for(i = 0; i < n; ++i) e[i].clear();
for(i = 0; i < n-1; ++i) {
scanf("%d %d %d", &x, &y, &w);
--x; --y;
e[x].push_back(Edge(y, w));
e[y].push_back(Edge(x, w));
}
solve();
}
return 0;
}