@Acqua
2019-01-25T01:21:33.000000Z
字数 1647
阅读 1164
动态规划 特殊技巧
题目来源
给定一棵有个结点的树，选取一个结点就能够支配与其直接相连的所有结点，求支配该树所有结点所需要选取的最小结点数。
启发式思维，
使用图论模板，树形。
表示结点被其父结点支配、被其自身支配、被其子结点支配。
如果结点被其父结点支配，就不可支配其子结点，
结点只能由其自身或其子结点支配。
。
如果结点被自己支配，其子结点都被父结点支配，但也可以被自己或子结点支配。
。
如果结点被其子结点支配，则必定要至少一个由自身支配，其余的可以由自己或子结点支配。为了保证强制选取且答案最优，用记录差值最小的[1]。
。
// La Pluie#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N=1505;struct edge{int v,next;}e[N<<1];int n,head[N],dp[N][3],k=1;void adde(int u,int v){e[k]=(edge){v,head[u]};head[u]=k++;}void dfs(int u,int f){int mn=2147483647;for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].v;if(v==f) continue;dfs(v,u);dp[u][0]+=min(dp[v][1],dp[v][2]);dp[u][1]+=min(dp[v][0],min(dp[v][1],dp[v][2]));mn=min(mn,dp[v][1]-min(dp[v][1],dp[v][2]));dp[u][2]+=min(dp[v][1],dp[v][2]);}dp[u][2]+=mn;}int main(){memset(head,-1,sizeof(head));scanf("%d",&n);for(int i=1;i<=n;i++){int u,v,ctrl;scanf("%d",&u);scanf("%d%d",&dp[u][0],&ctrl);for(int j=1;j<=ctrl;j++){scanf("%d",&v);adde(u,v);adde(v,u);}}dfs(1,0);printf("%d\n",min(dp[1][1],dp[1][2]));return 0;}