UVa12093 Protecting Zonk

本文主要是介绍UVa12093 Protecting Zonk，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

        题意：给定一个有n个节点的无根树，有两种装置A和B，每种都有无限多个。在某个节点X使用A装置需要C1的花费，并且此时与节点X相连的边都被覆盖。在某个节点X使用B装置需要C2的花费，并且此时与节点X相连的边以及与X相连的点相连的边都被覆盖。求覆盖所有边的最小花费。

        思路：树型dp。随便拿一个点当作树根，dp(i,j,k)，i代表节点号，j代表选择装置的类型，k代表覆盖状态，数组存该状态下最小花费。其中j=0：不部署装置，j=1：部署A装置，j=2：部署b装置。k=0：当前节点与父节点连接的边没有覆盖，k=1：覆盖了当前节点与父节点连接的边，k=2：覆盖了当前节点与父子节点连接的边，k=3：覆盖了当前节点与父节点，子孙节点连接的边。

#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <iomanip>    
#include <cstdlib>    
#include <string>    
#include <memory.h>    
#include <vector>    
#include <queue>    
#include <stack>    
#include <map>  
#include <set>  
#include <ctype.h>    
#define INF 10000000
#define ll long long
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010using namespace std;  vector<int> E[10010];
int dp[10010][3][4];
int n,c1,c2;inline int fun(int u,int f,int type,int statu){if(dp[u][type][statu]!=-1)return dp[u][type][statu];int re=0;if(statu==0){re=INF;int tmp=0;for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;tmp+=min3( fun(E[u][i],u,0,1) , fun(E[u][i],u,1,2) ,fun(E[u][i],u,2,3) );}for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;re=min(re,tmp-min3( fun(E[u][i],u,0,1) , fun(E[u][i],u,1,2) ,fun(E[u][i],u,2,3) )+fun(E[u][i],u,2,3));}}else{for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;re+=min3( fun(E[u][i],u,0,statu-1) , fun(E[u][i],u,1,2) ,fun(E[u][i],u,2,3) );}int tmp=0;for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;tmp+=min3( fun(E[u][i],u,0,1) , fun(E[u][i],u,1,2) ,fun(E[u][i],u,2,3) );}for(int i=0;i<E[u].size();i++){if(E[u][i]==f)continue;re=min(re,tmp-min3( fun(E[u][i],u,0,1) , fun(E[u][i],u,1,2) ,fun(E[u][i],u,2,3) )+fun(E[u][i],u,2,3));}}if(type==1)re+=c1;if(type==2)re+=c2;dp[u][type][statu]=re;return re;
}int main(){std::ios::sync_with_stdio(false);std::cin.tie(0);while(cin>>n>>c1>>c2){if(n==0&&c1==0&&c2==0)break;memset(dp,-1,sizeof(dp));for(int i=1;i<=n;i++)E[i].clear();//int u,v;for(int i=1;i<n;i++){cin>>u>>v;E[u].push_back(v);E[v].push_back(u);}int ans=min3( fun(1,-1,0,1) , fun(1,-1,1,2) , fun(1,-1,2,3)  );cout<<ans<<endl;}return 0;
}

这篇关于UVa12093 Protecting Zonk的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---