Capturing a country
http://acm.hdu.edu.cn/showproblem.php?pid=4340
Problem Description
Ant and Bob two army want to capture a country. The country is consist of N cities. To capture the city i, it takes Ant A[i] minutes, and Bob needs B[i] minutes to capture city i. Due to the similarity of neighboring cities, If the city
i and j are neighboring cities, if Ant has captured city i, then the time for Ant to capture city j is A[j]/2. Of course if Ant has captured city j, then the time for Ant to capture city i is A[i]/2. It is the same for Bob. We define
the total time to capture a country be the time to capture city 1 + the time to capture city 2 + ... + the time to capture city N. Now we want to know the minimal total time.
For simplicity, we assume that there is only one path to go from one city to another city.
i and j are neighboring cities, if Ant has captured city i, then the time for Ant to capture city j is A[j]/2. Of course if Ant has captured city j, then the time for Ant to capture city i is A[i]/2. It is the same for Bob. We define
the total time to capture a country be the time to capture city 1 + the time to capture city 2 + ... + the time to capture city N. Now we want to know the minimal total time.
For simplicity, we assume that there is only one path to go from one city to another city.
Input
The first line contains a integer N(0<N<100), which is the number of cities.Then following N lines describe A[1], A[2], …, A[N];Then following N lines describe B[1], B[2], …, B[N];Next comes
N-1 lines, each contains two integers x, y, meaning that city x and city y are neighboring.
N-1 lines, each contains two integers x, y, meaning that city x and city y are neighboring.
Output
Just output the minimal total time in a single line.
Sample Input
3 1 2 5 3 8 1 1 2 1 3
Sample Output
3
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define MAX 105
#define inf ((1<<30)-1)
int a[MAX],b[MAX];
int dp[MAX][2][2];
//dp[i][0][0] 代表A占领i点，i点取一半且树不完整
//dp[i][0][1] 代表A占领i点，树完整
//dp[i][1][0] 代表B占领i点，i点取一半且树不完整
//dp[i][1][1] 代表B占领i点，树完整
vector<int> edge[MAX];
void dfs(int x,int pre)
{
int k,childMin[2],childRoot[2];
//存储子树一半值的和
childMin[0]=childMin[1]=0;
//存储子树中非根结点的结点的最小值
childRoot[0]=childRoot[1]=inf;
//初始化
dp[x][0][0]=(a[x]>>1);
dp[x][1][0]=(b[x]>>1);
dp[x][0][1]=a[x];
dp[x][1][1]=b[x];
//树叶且不是树根时返回
if(edge[x].size()==1&&pre!=0) return;
for(int i=0;i<edge[x].size();++i)
{
k=edge[x][i];
if(k==pre) continue;
dfs(k,x);
childMin[0]+=min(dp[k][0][0],dp[k][1][1]);
childMin[1]+=min(dp[k][0][1],dp[k][1][0]);
//min(dp[k][0][0],dp[k][1][1])是选入最优解里面的，然后由根据此求出非根结点的最小代价入口
childRoot[0]=min(childRoot[0],dp[k][0][1]-min(dp[k][0][0],dp[k][1][1]));
//min(dp[k][1][0],dp[k][0][1])是选入最优解里面的，然后由根据此求出非根结点的最小代价入口
childRoot[1]=min(childRoot[1],dp[k][1][1]-min(dp[k][1][0],dp[k][0][1]));
}
dp[x][0][0]+=childMin[0];
dp[x][1][0]+=childMin[1];
dp[x][0][1]=min(childMin[0]+a[x],childMin[0]+(a[x]>>1)+childRoot[0]);
dp[x][1][1]=min(childMin[1]+b[x],childMin[1]+(b[x]>>1)+childRoot[1]);
}
int main()
{
int n,x,y;
for(;~scanf("%d",&n);)
{
for(int i=0;i<=n;++i) edge[i].clear();
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i) scanf("%d",&b[i]);
for(int i=1;i<n;++i)
{
scanf("%d%d",&x,&y);
edge[x].push_back(y);
edge[y].push_back(x);
}
dfs(1,0);
printf("%d\n",min(dp[1][0][1],dp[1][1][1]));
}
return 0;
}