@Acqua
2019-01-25T01:49:58.000000Z
字数 1527
阅读 924
动态规划 特殊技巧 独立解题
给定一棵有个结点的树，选取一个结点就能够支配与其直接相连的所有结点，求支配该树所有结点所需要选取的最小结点数。
启发式思维，
使用图论模板，树形。
表示结点被其父结点支配、被其自身支配、被其子结点支配。
如果结点被其父结点支配，就不可支配其子结点，
结点只能由其自身或其子结点支配。
。
如果结点被自己支配，其子结点都被父结点支配，但因为服务器可以相连，所以也可以由自己支配。
。
如果结点被其子结点支配，则必定要有且仅有一个由自身支配，其余的只能由其子结点支配。记录，用额外费用差值最小的代替。
。
初始化：。
// La Pluie#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;const int N=1e4+5;struct edge{int v,next;}e[N<<1];int head[N],k,dp[N][3],n;void adde(int u,int v){e[k]=(edge){v,head[u]};head[u]=k++;}void dfs(int u,int f){int mn=1e4+1;dp[u][1]=1;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],dp[v][1]);dp[u][2]+=dp[v][2];mn=min(mn,dp[v][1]-dp[v][2]);}dp[u][2]+=mn;}int main(){while(~scanf("%d",&n)){memset(head,-1,sizeof(head));memset(dp,0,sizeof(dp));k=1;for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);adde(u,v);adde(v,u);}int x;scanf("%d",&x);dfs(1,0);// for(int i=1;i<=n;i++) printf("%d %d %d\n",dp[i][0],dp[i][1],dp[i][2]);printf("%d\n",min(dp[1][1],dp[1][2]));if(x==-1) break;}return 0;}