傳送門

DP

題目講得很清楚"對于電路板的任何兩個節(jié)點，都存在且僅存在一條通路".

所以電路板是一顆樹

題目要求葉子節(jié)點時態(tài)一致

如果從根開始枚舉時間肯定超時

考慮反過來

從葉子節(jié)點開始考慮時間

容易注意到

對于一個子樹的根 root 來說

不管上面用了多久把信息傳下來

要讓它的兒子收到信息的時間相同

就必須讓 root 到各個兒子的距離相等

如果一個子樹已經調好了

那么以后也不會再去更改

即無后效性

所以考慮DP

對于一個非葉子節(jié)點，要讓它到各個兒子的距離相等

那么顯然最節(jié)省的方案就是

讓它到各個兒子的距離改成它最遠的兒子的距離

所以得出狀態(tài)轉移方程：

設f[ i ]為 當以 i 為根的子樹的時態(tài)同步時，從它的葉子到 i 需要的時間

則

f[ i ]=max(f[ i ],f[ u ]+dis[ i ][ u ]) ( u為 i 的兒子，dis[ i ][ u ]為 i 到 u 的距離)

而答案就在更新f[ i ] 的時候順便累加一下就好了

?

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<vector> using namespace std; inline 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<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; } const int N=500007; vector <int> v[N],g[N]; //用vector 存圖，反正不會超時 int n,rt;//rt 為根節(jié)點 long long f[N],ans;//f如上所述，ans存答案 inline void dfs(int x,int fa)//fa 存 x 的父親 {int len=v[x].size();for(int i=0;i<len;i++){int u=v[x][i];if(u==fa) continue;//如果是父親就跳過dfs(u,x);//否則先更新兒子節(jié)點f[x]=max(f[x],f[u]+g[x][i]);//更新當前節(jié)點}for(int i=0;i<len;i++){int u=v[x][i];if(u==fa) continue;//如果是父親就跳過ans+=(f[x]-f[u]-g[x][i]);//累加答案} } int main() {int a,b,c;cin>>n>>rt;for(int i=1;i<n;i++){a=read(); b=read(); c=read();v[a].push_back(b); g[a].push_back(c);v[b].push_back(a); g[b].push_back(c);}//存邊dfs(rt,rt);cout<<ans;return 0; }

?

轉載于:https://www.cnblogs.com/LLTYYC/p/9523875.html

總結

以上是生活随笔為你收集整理的P1131 [ZJOI2007]时态同步的全部內容，希望文章能夠幫你解決所遇到的問題。

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