2435: [Noi2011]道路修建

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?3115??Solved:?1002
[Submit][Status][Discuss]

Description

在 W 星球上有 n 個國家。為了各自國家的經濟發展，他們決定在各個國家
之間建設雙向道路使得國家之間連通。但是每個國家的國王都很吝嗇，他們只愿
意修建恰好 n – 1條雙向道路。 每條道路的修建都要付出一定的費用， 這個費用等于道路長度乘以道路兩端的國家個數之差的絕對值。例如，在下圖中，虛線所示道路兩端分別有 2 個、4個國家，如果該道路長度為 1，則費用為1×|2 – 4|=2。圖中圓圈里的數字表示國家的編號。

由于國家的數量十分龐大，道路的建造方案有很多種，同時每種方案的修建
費用難以用人工計算，國王們決定找人設計一個軟件，對于給定的建造方案，計
算出所需要的費用。請你幫助國王們設計一個這樣的軟件。

Input

輸入的第一行包含一個整數n，表示 W 星球上的國家的數量，國家從 1到n
編號。接下來 n – 1行描述道路建設情況，其中第 i 行包含三個整數ai、bi和ci，表
示第i 條雙向道路修建在 ai與bi兩個國家之間，長度為ci。

Output

輸出一個整數，表示修建所有道路所需要的總費用。

Sample Input

6
1 2 1
1 3 1
1 4 2
6 3 1
5 2 1

Sample Output

20

HINT

n = 1,000,000 1≤ai, bi≤n?
0 ≤ci≤ 10^6

Source

Day2

Solution

看WC的講義上似乎樹形DP中有此題...

然而，直接暴力的DFS求出每個節點的size[u]，那么另一邊的size[v]=n-size[u]

那么可以直接累計答案...

坑點：注意轉longlong，（abs中間也要強轉longlong..雖然不明覺厲）

Code

#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> using namespace std; int read() {int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; } #define maxn 1100000 int n;long long ans; struct EdgeNode{int next,to,from,len;}edge[maxn<<1]; int head[maxn],cnt; void add(int u,int v,int w) {cnt++;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt;edge[cnt].len=w;edge[cnt].from=u; } void insert(int u,int v,int w) {add(u,v,w); add(v,u,w);} int size[maxn]; void DFS(int now,int fa,long long dis) {size[now]=1;for (int i=head[now]; i; i=edge[i].next)if (edge[i].to!=fa){DFS(edge[i].to,now,(long long)edge[i].len);size[now]+=size[edge[i].to];}ans+=(long long)(dis*(long long)abs((long long)(size[now]-(n-size[now])))); } int main() {n=read();for (int u,v,w,i=1; i<=n-1; i++)u=read(),v=read(),w=read(),insert(u,v,w);DFS(1,0,0LL);printf("%lld\n",ans);return 0; }

一開始想到WC的講義上的樹形DP，那么考慮樹形DP..想了想，size這個東西是不是可以直接DFS出來，直接算答案啊？難道有反例？于是劃拉了幾個確定似乎沒有，然后試了試愉快的AC了...SMG

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5506671.html

總結

以上是生活随笔為你收集整理的【BZOJ-2435】道路修建 （树形DP？）DFS的全部內容，希望文章能夠幫你解決所遇到的問題。

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