【原题题面】传送门
【题解大意】
乍一看感觉以为网络流表示一点都不会不会不会。
然后发现可以树形dp搞一下。
再然后知道了换根dp。
设d[x]表示以x为根的子树中把x做为源点，从x出发流向子树的流量最大是多少。
d[x] += min(d[y],z);(deg[y]!=1)
d[x] = z; (deg[y]==1)
f[x]表示以x做为源点，从x出发流向整个水系的流量最大是多少。
f[y] = d[y] + min(f[x] - min(d[y],z));(deg[x]!=1)
f[y] = d[y] + z;
【code】
暴力：
#include<bits/stdc++.h> using namespace std; #define File "degree" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } 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-'0'; ch = getchar();} return x * f; } const int mxn = 2e5+3; int n; struct edge{ int nxt,y,v; }e[mxn<<1]; int to[mxn],len; inline void add(int xx,int yy,int vv){ e[++len].nxt = to[xx]; to[xx] = len; e[len].y = yy; e[len].v = vv; } bool v[mxn]; int d[mxn],deg[mxn]; inline void dp(int x){ v[x] = 1; d[x] = 0; for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y,z = e[i].v; if(v[y]) continue; dp(y); if(deg[y]==1) d[x] += z; else d[x] += min(d[y],z); } } int T; int main(){ // file(); T = read(); while(T--){ n = read(); len = 1; memset(v,0,sizeof v); memset(d,0,sizeof d); memset(to,0,sizeof to); memset(deg,0,sizeof deg); for(int i = 1;i < n; ++i){ int x = read(),y = read(),z = read(); add(x,y,z),add(y,x,z); deg[x]++,deg[y]++; } int ans(0); for(int i = 1;i <= n; ++i){ memset(d,0,sizeof d); memset(v,0,sizeof v); dp(i); ans = max(ans,d[i]); } printf("%d ",ans); } return 0; }
标程：
#include<bits/stdc++.h> using namespace std; #define File "degree" #define ll long long inline void file(){ freopen(File".in","r",stdin); freopen(File".out","w",stdout); } 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-'0'; ch = getchar();} return x * f; } const int mxn = 2e5+3; int T,n; struct edge{ int nxt,y,v; }e[mxn<<1]; int to[mxn],len; inline void add(int xx,int yy,int vv){ e[++len].nxt = to[xx]; to[xx] = len; e[len].y = yy; e[len].v = vv; } /* 1 5 1 2 11 1 4 13 3 4 5 4 5 10 */ bool v[mxn]; int d[mxn],deg[mxn],f[mxn]; inline void dp(int x){ v[x] = 1; d[x] = 0; for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y,z = e[i].v; if(v[y]) continue; dp(y); if(deg[y]==1) d[x] += z; else d[x] += min(d[y],z); } } inline void dfs(int x){ v[x] = 1; for(int i = to[x]; i;i = e[i].nxt){ int y = e[i].y,z = e[i].v; if(v[y]) continue; if(deg[x]==1) f[y] = d[y] + z; else f[y] = d[y] + min(f[x] - min(d[y],z),z); dfs(y); } } int main(){ // file(); T = read(); while(T--){ n = read(); len = 1; memset(v,0,sizeof v); memset(f,0,sizeof f); memset(d,0,sizeof d); memset(deg,0,sizeof deg); memset(to,0,sizeof to); for(int i = 1;i < n; ++i){ int x = read(),y = read(),z = read(); add(x,y,z),add(y,x,z); deg[x]++,deg[y]++; } int rt(1); dp(rt); memset(v,0,sizeof v); f[rt] = d[rt]; dfs(rt); int ans(0); for(int i = 1;i <= n; ++i) ans = max(ans,f[i]); printf("%d ",ans); } return 0; }