题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
//#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
const int INF=0x3f3f3f3f;
int h[N],to[N*2],w[N*2],ne[N*2],tot;
int d[N],f[N],deg[N];
int n;
void add(int a,int b,int c){
to[++tot]=b,w[tot]=c,ne[tot]=h[a],h[a]=tot;
}
int dfs_d(int u,int fa){
for(int i=h[u];i;i=ne[i]){
int v=to[i];
if(v==fa)continue;
int s=dfs_d(v,u);
d[u]+=min(w[i],s);
}
if(deg[u]==1)return INF;
return d[u];
}
int dfs_f(int u,int fa){
for(int i=h[u];i;i=ne[i]){
int v=to[i];
if(v==fa)continue;
if(deg[u]==1)f[v]=d[v]+w[i];
else f[v]=d[v]+min(w[i],f[u]-min(w[i],d[v]));
dfs_f(v,u);
}
}
void solve(){
cin>>n;
tot=0;
memset(h,0,sizeof h);
memset(d,0,sizeof d);
memset(f,0,sizeof f);
memset(deg,0,sizeof deg);
for(int i=1;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
deg[a]++,deg[b]++;
}
dfs_d(1,-1);
f[1]=d[1];
dfs_f(1,-1);
int ans=0;
for(int i=1;i<=n;i++)ans=max(ans,f[i]);
cout<<ans<<endl;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int _=1;
cin>>_;
for(int i=1;i<=_;i++){
solve();
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla