hihocoder 1035 自驾旅行 III(树形dp)

自驾旅行 III(树形dp)"/>

hihocoder 1035 自驾旅行 III(树形dp)

本蒟蒻一道树形dp做了一天，OrzOrzOrz.....菜得难以启齿～～

题解的话这篇博客说得听清楚的～～～

附上大佬的链接：点击打开链接

同时附上本苣菜的代码吧～～

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=0x3f3f3f3f3f3f3f3f;
const int MAXN=1000100;
struct edge_t
{int v,next;LL c0,c1;
}edge[MAXN*2];
int head[MAXN];
int tot;
void init()
{tot=0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v,LL c0,LL c1)
{edge[tot].v=v;edge[tot].c0=c0;edge[tot].c1=c1;edge[tot].next=head[u];head[u]=tot++;
}
//每到一个节点，分情况讨论
//首先没车:
//      分为两种情况:
//      (1).步行出门且回来
//      (2).步行出门人不回来
//如果有车
//      分为三种情况:
//      (1).可以开车出门(开车次数>=0)，且如果骑车，人车都回来，否则人必须回来
//      (2).可以开车出门(开车次数>=1)，车可以不用回来，但人必须回来
//      (3).可以开车出门(开车次数>=1)，车可以没有回来，人也可以没有回来
#define on_foot_ret 0
#define on_foot_noret 1
#define car_people 2
#define nocar_people 3
#define nocar_nopeople 4
bool imp[MAXN];
LL dp[MAXN][5];
void debug(int u)
{printf("Vertex :%d\n",u);printf("On_foot_ret :%lld\n",dp[u][0]);printf("On_foot_noret :%lld\n",dp[u][1]);printf("Car_people :%lld\n",dp[u][2]);printf("Nocar_people :%lld\n",dp[u][3]);printf("Nocar_Nopeople :%lld\n",dp[u][4]);putchar('\n');
}
bool useful[MAXN];
void dfs(int u,int fa)
{useful[u]=imp[u]?true:false;LL chajia1=0;LL chajia2=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==fa) continue;LL c0=edge[i].c0;LL c1=edge[i].c1;dfs(v,u);if(useful[v]){useful[u]=true;dp[u][on_foot_ret]+=(dp[v][on_foot_ret]+2*c0);chajia1=max(chajia1,dp[v][on_foot_ret]+c0-dp[v][on_foot_noret]);dp[u][car_people]+=min(dp[v][on_foot_ret]+2*c0,dp[v][car_people]+2*c1);chajia2=max(chajia2,min(dp[v][on_foot_ret]+2*c0,dp[v][car_people]+2*c1)-(dp[v][nocar_people]+c0+c1));}}dp[u][on_foot_noret]=dp[u][on_foot_ret]-chajia1;dp[u][nocar_people]=dp[u][car_people]-chajia2;//ttf1表示选择nocar_people，ttf2表示on_foot_noret(遍历最后一个子树的时候没车了)//same表示遍历最后一棵子树的时候还有车LL ttf1=0,ttf2=0,same=0;int match1=-1,match2=-1;LL prettf1=0,prettf2=0;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==fa) continue;LL c0=edge[i].c0;LL c1=edge[i].c1;if(useful[v]){LL tmp1=min(dp[v][on_foot_ret]+2*c0,dp[v][car_people]+2*c1)-(dp[v][nocar_people]+c0+c1);LL tmp2=min(dp[v][on_foot_ret]+2*c0,dp[v][car_people]+2*c1)-(dp[v][on_foot_noret]+c0);LL tmp3=min(dp[v][on_foot_ret]+2*c0,dp[v][car_people]+2*c1)-min(dp[v][on_foot_noret]+c0,dp[v][nocar_nopeople]+c1);//ttf1和ttf2不能属于同一棵子树if(tmp1>=ttf1){match1=v;prettf1=ttf1;ttf1=tmp1;}else if(tmp1>prettf1) prettf1=tmp1;if(tmp2>=ttf2){match2=v;prettf2=ttf2;ttf2=tmp2;}else if(tmp2>prettf2) prettf2=tmp2;same=max(same,tmp3);}}LL temp;if(match1!=match2) temp=ttf1+ttf2;else temp=max(ttf1+prettf2,ttf2+prettf1);dp[u][nocar_nopeople]=dp[u][car_people]-max(temp,same);//    if(useful[u]) debug(u);}
int main()
{
//    freopen("in.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF){memset(dp,0,sizeof(dp));memset(imp,false,sizeof(imp));memset(useful,false,sizeof(useful));init();for(int i=1;i<n;i++){int u,v;LL c0,c1;scanf("%d%d%lld%lld",&u,&v,&c0,&c1);addedge(u,v,c0,c1);addedge(v,u,c0,c1);}int w;scanf("%d",&w);for(int i=1;i<=w;i++){int flag;scanf("%d",&flag);imp[flag]=true;}int root=1;dfs(root,-1);printf("%lld\n",min(dp[root][on_foot_noret],dp[root][nocar_nopeople]));}return 0;
}