文章目錄

• • 題目描述
  • 樣例分析：
  • 題意：
  • 題解：
  • 代碼：

本題目傳送

題目樹學是這個題的簡易版，也涉及換根問題，可以先看看這個
樹學

時間限制：C/C++ 1秒，其他語言2秒 空間限制：C/C++ 32768K，其他語言65536K 64bit
IO Format:%lld

題目描述

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.

輸入描述:
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.
輸出描述:
For each test case, output the result on a single line.
示例1
輸入

1 5 1 2 11 1 4 13 3 4 5 4 5 10

輸出

26

題意：

看看樣例分析應該就明白了
每個節點都有流量，求出最大流量是多少？

題解：

flow【i】表示i點的流量：
一個點的流量是怎么來的？如果j（j是i的子節點）的流量小于i與j邊的容量，flow【i】=flow[j]，如果大于兩點之間的容量，flow[i]=i與j的流量
i與j的流量就是i與j的邊權，我們用edge[i][j]表示。
可以得到公式：flow[i]=∑min(flow[j],edge[i][j])
因為i有可能有很多子節點，所以加在一起
考慮完i之后，我們來考慮換根
如圖：
我們將根從x換成y
題一中（以x為根）
x的流量來自于y，子樹2，子樹3
y的流量來自于子樹1
圖二中（以y為根）
x的流量來自子樹2，子樹3
y的流量來自子樹1，x

我們發現換根后，x的流量就沒有了y的部分，其他都還在，此時x的流量就是原本的減去從y流向x的部分，new[x]=flow[ x ] - min ( flow[ y ] , edge[ x ] [ y ] ),這個new表示x新的流量

我們再看y，y的流量多了從x流來的部分，y的流量就是flow[y]+min(new[x],edge[x][y])，，因為換根x的流量發生改變（上一段所講），那流向y的是現在x的流量，而不是換跟前的flow[x].

換根前后，圖二中綠色區域沒有發生改變，也就是父節點改變影響不到子節點

還要注意葉子節點，如果x從根變成葉子節點（x的兒子只有y，當y成為根節點之后，x沒有了兒子），x的流量不是上面的公式，而是變成了edge[x][y]，因為沒有子節點的流量流向x，只有x與y的邊權值，也就是上面講的式子使用條件是min（x，y），x和y不能為0。

先求出x為根的流量，然后依次換根求出最大值

代碼：

#include <bits/stdc++.h>#define inf 0x7f typedef long long LL; using namespace std; const int maxn = 2e5 + 3;int n;int head[maxn], cnt = 0, d[maxn], deg[maxn], f[maxn]; struct edge{int x, y;int next;int w; }edge[maxn * 2];void init() { cnt = 0;memset(head, -1, sizeof(head));memset(d, 0, sizeof(d));memset(deg, 0, sizeof(deg)); }void addedge(int x, int y, int w) {edge[cnt].x = x;edge[cnt].y = y;edge[cnt].w = w;edge[cnt].next = head[x];head[x] = cnt++;}void dfs(int root, int fa) {int ans = 0;for(int i = head[root]; i != -1; i = edge[i].next){int y = edge[i].y;if(y == fa){continue;}if(deg[y] == 1){//如果y只有一個子節點，y的流量只能是root與y的邊權值 ans += edge[i].w;}else{dfs(y, root);ans += min(d[y], edge[i].w);}}d[root] = ans return ; }//先求出節點x的流量 void dp(int x, int fa) {for(int i = head[x]; i != -1; i = edge[i].next){int y = edge[i].y;if(edge[i].y == fa)continue;if(deg[x] == 1){f[y] = d[y] + edge[i].w;}else{f[y] = d[y] + min(f[x] - min(d[y], edge[i].w), edge[i].w);//核心公式 }dp(y, x);} }//從x不斷換根 int main() {int t;cin>>t;int x, y, w;while(t--){init();//初始化 scanf("%d", &n);for(int i = 0; i < n - 1; i++){scanf("%d%d%d", &x, &y, &w);addedge(x, y, w);//添邊 addedge(y, x, w);//添邊 deg[x]++;//deg用于判斷這個點有幾個子節點 deg[y]++;}int s = 1;dfs(s, 0);//求x的流量 f[s] = d[s];dp(s, 0);//不斷換根 int ans = 0;for(int i = 1; i <= n; i++){ans = max(ans, f[i]);}printf("%d\n", ans);}return 0; }

總結

以上是生活随笔為你收集整理的牛客网【每日一题】4月13号 Accumulation Degree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。