/**//* 题意:一棵树,A机器人能保护邻接的边及邻接点的邻接边 B机器人只能保护邻接的边 A,B机器人花费不同 求最小的代价保护所有的边 状态: A[u]: u的父边、爷爷边,及子树都能被保护 costA+∑min(A[v],B[v],C[v],D[v]) B[u]: u的父边,及子树都能被保护 两种情况:u放一个机器人B costB+∑min(A[v],B[v],C[v]) 至少一个v放一个机器人A ∑min(A[v],B[v],C[v])(至少一个A) C[u]: u的子树都能被保护 解题报告是直接 ∑min(A[v],B[v]) 我觉得有一种情况是某个v有A,有些有C,这样就可以覆盖到了 D[u]: u的某些儿子的边能被保护,但儿子的子树能被保护 ∑min(B[v],C[v]) */ #include<cstdio> #include<vector> #include<algorithm> #include<cstring> using namespace std;
const int MAXN = 10010; const int INF = 1000000000;
vector<int>G[MAXN]; int A[MAXN],B[MAXN],C[MAXN],D[MAXN]; int costA,costB,n;
void dfs(int u,int p) { A[u]=costA; B[u]=0; C[u]=0; D[u]=0; int son=0; bool flagB=true; int cntC=0,cntA=0; for(int i=0,size=G[u].size();i<size;i++) { int v=G[u][i]; if(v==p)continue; dfs(v,u); A[u]+=min(min(A[v],B[v]),min(C[v],D[v])); if(A[v]<min(B[v],C[v]))flagB=false; B[u]+=min(A[v],min(B[v],C[v])); if(A[v]<B[v]&&A[v]<C[v])cntA++; if(C[v]<B[v]&&C[v]<A[v])cntC++; C[u]+=min(A[v],min(B[v],C[v])); D[u]+=min(B[v],C[v]); } if(flagB)//没有A时 { int Min=INF; for(int i=0,size=G[u].size();i<size;i++) { int v=G[u][i]; if(v==p)continue; Min=min(Min,A[v]-min(B[v],C[v]));//选择一个A } B[u]+=min(Min,costB);//点u放机器人B } if(cntC&&!cntA)//如果有C但没有A时 { int Min=INF,tot=0; for(int i=0,size=G[u].size();i<size;i++) { int v=G[u][i]; if(v==p)continue; if(C[v]<B[v]){tot+=B[v]-C[v];}//可以将全部的C换为B Min=min(Min,A[v]-min(B[v],C[v]));//可以选择一个A } C[u]+=min(Min,tot); } //printf("%d %d %d %d %d\n",u,A[u],B[u],C[u],D[u]); } int main() { //freopen("in","r",stdin); while(scanf("%d%d%d",&n,&costB,&costA),n) { for(int i=1;i<=n;i++) G[i].clear(); for(int i=1,v,u;i<n;i++) { scanf("%d%d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs(1,1); printf("%d\n",min(min(A[1],B[1]),C[1])); } return 0; }
|