每日一题居然放了一个简单题。
题意:
给一个无向图,n个点n-1条边,每条边上有边权,现在给定一个根s,求以s为根的图中,删掉一些边要让所有度为1的点不能连接到s。
思路:
根据题意,给出的图就是一颗树。那么就是问删一些边让叶子节点无法连通到根s。
我们可以考虑某个点x,假设要让x子树的叶子节点无法连通s,我们要么删x-s这条边,要么删除x子树中的边。
那么我们可以dfs,我们维护f[x]为以x为根让叶子节点无法连接到x的最小删边代价。
显然,枚举x中的所有相连节点v,可以得到转移方程:
f[x]=min(w(x,v),f[v])
注意叶子节点的时候只能选删叶子节点边。
O(n)可以解决。
代码:
#include<bits/stdc++.h> using namespace std; int n,m,s; int tot,head[100005],vis[100005]; struct node{ int w,next,to; }p[200050]; void init(){ memset(head,-1,sizeof(head)); } void add(int x,int y,int z){ tot++; p[tot].to=y; p[tot].next=head[x]; p[tot].w=z; head[x]=tot; } long long dfs(int x){ vis[x]=1; long long ans=0; for(int i=head[x];~i;i=p[i].next){ int y=p[i].to; if(vis[y])continue; vis[y]=1; int w=p[i].w; long long tmp=dfs(y); if(tmp==-1)ans+=w; else ans+=min(1ll*w,tmp); } if (ans==0)return -1; //到叶子节点了。 return ans; } int main() { cin>>n>>m>>s; init(); for(int i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } cout<<dfs(s)<<endl; return 0; }