原谅我前面一题每日一题没做。
数学啊数学,太难了啊。。
来看这里的每日一题,看到题目以为是网络流,直接点开了题解。发现推荐做201400树学。
好的,那么先来看树学。
链接:https://ac.nowcoder.com/acm/problem/201400
题目大意:
给一棵树,可以找一个点作为根,然后计算出深度和。问如果选根让深度和最小,求这个最小值。
数据范围n<=1e6
思路:
这个数据量肯定是考虑线性复杂度了。
显然,如果指定一个点作为根,我们是可以在O(n)时间上计算出∑dep[i]。
如果在这个基础上枚举根,就要再乘一个n,显然不可接受。
那能不能在枚举根的时候,O(1)的计算出答案呢?让我们考虑根转移的时候的情况:
假设从u->v,如果我们已经计算出了f[u]表示以u为根的答案。
显然u和u上方的节点dep+1,v和v下方的节点dep-1,那么我们可以得到转移方程:
f[v]=f[u]+u及u上方的节点数量-v及v下方的节点数量
这里我们可以先跑一边dfs,用son[x]表示x的子树节点数量(包括x)。
因此我们在重新写一遍转移方程为:
f[v]=f[u]+(n-son[v])-son[v]
两次dfs就好了。
复杂度O(n)
代码:
#include<bits/stdc++.h> using namespace std; int n,son[1000050],dep[1000050]; long long ans,f[1000050]; vector<int>vt[1000040]; int dfs(int x,int fa){ son[x]=1; for(int i=0;i<vt[x].size();i++){ int y=vt[x][i]; if(y==fa)continue; dep[y]=dep[x]+1; son[x]+=dfs(y,x); } ans+=dep[x]; return son[x]; } int minw=0x3f3f3f3f; void dfs2(int x,int fa){ for(int i=0;i<vt[x].size();i++){ int y=vt[x][i]; if(y==fa)continue; f[y]=f[x]+n-son[y]-son[y]; dfs2(y,x); } } int main() { cin>>n; for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); vt[x].push_back(y); vt[y].push_back(x); } dfs(1,-1); f[1]=ans; dfs2(1,-1); for(int i=2;i<=n;i++)ans=min(ans,f[i]); cout<<ans<<endl; return 0; }
再来看这道题目:
题目大意:
给一棵树,每条边上有一个容量,从某个点出发一直到叶子节点,可以计算出最大的容量。这里的容量不能超过路劲上任意一条边的容量。令A(x)表示从点x出发到所有它子树的叶子的容量和的最大值。
思路:
有了上一题,我们可以参考刚刚的思路。
首先定一个根节点1,我们可以计算出A[1]的值。
这里我们可以用一个dfs来解决,A[1]=∑min(w(1,v),A[v])
注意,这么计算的A[x]同上题是一样的,即A[x]只能表示从x出发向下的容量和,x上方的我们没有计算到。
显然一遍dfs以后,我们预处理出了A[x],并且只有A[1]是包括所有子树的答案。
接着我们考虑u->v的转移了:
显然从u到v,现在变成了以v为中心去计算,考虑v的上方,显然我们有
A[u]-min(w(u,v),A[v])
注意:由于v是从u转移过来的,此时的A[u]已经是包括了所有子树的答案
然后是v的下方,就是A[v]
那么我们有:
A[v]=min(w(u,v),A[u]-min(w(u,v),A[v]) )+A[v]
注意到叶子节点的时候要特殊处理一下,因为叶子节点下方没有东西了。
代码:
#include<bits/stdc++.h> using namespace std; int n,d[200050]; long long A[200040],ans; struct node{ int to,w,next; }p[400050]; int tot,head[200050]; void init() { tot=0; for(int i=0;i<400050;i++)p[i].next=-1; memset(head,-1,sizeof(head)); memset(A,0,sizeof(A)); memset(d,0,sizeof(d)); } void add(int a,int b,int c){ tot++; p[tot].to=b; p[tot].w=c; p[tot].next=head[a]; head[a]=tot; } long long dfs(int x,int fa){ for(int i=head[x];~i;i=p[i].next){ int y=p[i].to; if(y==fa)continue; if(d[y]==1)A[x]+=p[i].w; //叶子节点的特殊处理,下方直接设置为流量边 else A[x]+=min(1ll*p[i].w,dfs(y,x)); } return A[x]; } void dfs2(int x,int fa){ for(int i=head[x];~i;i=p[i].next){ int y=p[i].to; if(y==fa)continue; if(d[y]==1)A[y]=min(1ll*p[i].w,A[x]-1ll*p[i].w); //叶子点处理 else A[y]=min(1ll*p[i].w,A[x]-min(1ll*p[i].w,A[y]))+A[y]; dfs2(y,x); } } int main() { int T; cin>>T; while(T--){ init(); int n; cin>>n; for(int i=1;i<n;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); d[x]++; d[y]++; } dfs(1,-1); ans=A[1]; // cout<<ans<<endl; dfs2(1,-1); for(int i=1;i<=n;i++)ans=max(ans,A[i]); cout<<ans<<endl; } return 0; }