题意:选取任意一个节点为根节点,求最大流通流量
题解:参考第二题所给的遍历方法和换根方法,进行换根即可,只不过换根是式子变为
, 表示第一次搜索的在v节点的值, 表示第v个节点的答案.
第二题参考链接:https://blog.nowcoder.net/n/036d85b25e8c4d8aab55351f6d7134ca
code:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e5+10; int t,n,hd[N],tot,vis[N],d[N],f[N],deg[N],ans; struct Edge{ int v,nx,w; }e[N<<1]; inline void add(int u,int v,int w) { e[tot].v=v; e[tot].w=w; e[tot].nx=hd[u]; hd[u]=tot++; } void dp(int u) { vis[u]=1; d[u]=0; for(int i=hd[u];~i;i=e[i].nx) { int v=e[i].v; if(vis[v])continue; dp(v); if(deg[v]==1)d[u]+=e[i].w; else d[u]+=min(d[v],e[i].w); } } void dfs(int u) { vis[u]=1; for(int i=hd[u];~i;i=e[i].nx) { int v=e[i].v; if(vis[v])continue; f[v]=d[v]+min(f[u]-min(d[v],e[i].w),e[i].w); dfs(v); } } int main() { scanf("%d",&t); while(t--) { memset(hd,-1,sizeof(hd)); memset(vis,0,sizeof(vis)); memset(f,0,sizeof(f)); memset(d,0,sizeof(d)); memset(deg,0,sizeof(deg)); tot=0;ans=0; scanf("%d",&n); int u,v,w; for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w),add(v,u,w);deg[u]++,deg[v]++; } dp(1); memset(vis,0,sizeof(vis)); f[1]=d[1]; dfs(1); for(int i=1;i<=n;i++) ans=max(ans,f[i]); printf("%d\n",ans); } return 0; }