ZOJ 3659 Conquer a New Region
Conquer a New Region
64-bit integer IO format: %lld Java class name: Main
The wheel of the history rolling forward, our king conquered a new region in a distant continent.
There are N towns (numbered from 1 to N) in this region connected by several roads. It's confirmed that there is exact one route between any two towns. Traffic is important while controlled colonies are far away from the local country. We define the capacity C(i, j) of a road indicating it is allowed to transport at most C(i, j) goods between town i and town j if there is a road between them. And for a route between i and j, we define a value S(i, j) indicating the maximum traffic capacity between i and j which is equal to the minimum capacity of the roads on the route.
Our king wants to select a center town to restore his war-resources in which the total traffic capacities from the center to the other N - 1 towns is maximized. Now, you, the best programmer in the kingdom, should help our king to select this center.
Input
There are multiple test cases.
The first line of each case contains an integer N. (1 ≤ N ≤ 200,000)
The next N - 1 lines each contains three integers a, b, c indicating there is a road between town a and town b whose capacity is c. (1 ≤ a, b ≤ N, 1 ≤ c ≤ 100,000)
Output
For each test case, output an integer indicating the total traffic capacity of the chosen center town.
Sample Input
4 1 2 2 2 4 1 2 3 1 4 1 2 1 2 4 1 2 3 1
Sample Output
4 3
Source
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 200100; 18 struct arc{ 19 int u,v,w; 20 arc(int x = 0,int y = 0,int z = 0){ 21 u = x; 22 v = y; 23 w = z; 24 } 25 }; 26 int uf[maxn],rank_[maxn],tot; 27 LL d[maxn]; 28 arc e[maxn]; 29 bool cmp(const arc &x,const arc &y){ 30 return x.w > y.w; 31 } 32 int Find(int x){ 33 if(x == uf[x]) return uf[x]; 34 return uf[x] = Find(uf[x]); 35 } 36 void Union(int x,int y,LL z){ 37 uf[x] = y; 38 rank_[y] += rank_[x]; 39 d[y] = z; 40 } 41 int main() { 42 int n; 43 while(~scanf("%d",&n)){ 44 for(int i = 1; i < n; i++) 45 scanf("%d %d %d",&e[i].u,&e[i].v,&e[i].w); 46 for(int i = 0; i < maxn; i++){ 47 uf[i] = i; 48 rank_[i] = 1; 49 d[i] = 0; 50 } 51 sort(e+1,e+n,cmp); 52 for(int i = 1; i < n; i++){ 53 int x = Find(e[i].u); 54 int y = Find(e[i].v); 55 LL sx = d[x] + (LL)e[i].w*rank_[y]; 56 LL sy = d[y] + (LL)e[i].w*rank_[x]; 57 if(sx > sy) Union(y,x,sx); 58 else Union(x,y,sy); 59 } 60 printf("%I64d\n",d[Find(1)]); 61 } 62 return 0; 63 }
相关文章
- PHP中new self()和new static()的区别
- 详解Python中的__new__、__init__、__call__三个特殊方法
- python笔记31-使用ddt报告出现dict() -> new empty dictionary dict(mapping) 问题解决
- SPOJ 705 New Distinct Substrings
- 测试/开发工程师周末该怎么度过?没对象的程序员我们就new一个.......
- c++中类型用new和不用new的区别
- CodeForces 723A The New Year: Meeting Friends (水题)
- CodeForces 611C New Year and Domino (动态规划,DP)
- The note of Developing Innovative Ideas for New Companies Course
- Vue--路由的基本使用(组件之间的跳转)new VueRouter---配置path和子组件---跳转路径带#<a href="#/register">---显示区域用<router-view>
- Announcing the Updated NGINX and NGINX Plus Plug‑In for New Relic (Version 2)
- java 虚方法。 后面new 那个类, 就调用哪个类的方法 ,而非定义类的方案。 关于父子 类的 呵呵
- iOS Xcode, 解决“Could not insert new outlet connection”的问题。
- Error Code: 1414. OUT or INOUT argument 2 for routine company.new_procedure is not a variable or NEW