本文共 1911 字，大约阅读时间需要 6 分钟。
1、
2、题目大意：
给出一棵无向树，每条边都有权值，已知根节点是r,现在要删除部分边，使得所有的叶子结点都不与根连通，求删掉的这些边的最小权值和是多少？
首先我们要从根节点开始遍历，从子节点更新到父节点，用dp[i]表示以i结点为根的子树保证子节点不连通最小代价和，那么dp[r]即所求
dp[i]+=min(w[i],dp[j]);dp[j]是i的子节点
if(v[i] != fa)//如果不判断是不是根节点，将导致无线循环，因为边是无向的，例如1是2的父节点，1调用2,2调用1,1再调用2.。。。。。 { flag = 1; dfs(v[i], cur); dp[cur] += min(w[i], dp[v[i]]); }
4、用vector存储树会导致栈溢出？？？参考网上的存储树的方法可AC
注意n=1的情况
5、AC代码：
#include#include #include #include using namespace std;#define N 2005#define INF 0x7fffffffint dp[N];int tmp=0;int e, next[N], v[N], w[N],adj[N];void add(int x, int y, int z){ v[e] = y, w[e] = z; next[e] = adj[x], adj[x] = e ++;}void dfs(int cur, int fa){ int i, flag = 0; dp[cur] = 0; for(i = adj[cur]; i != -1; i = next[i]) if(v[i] != fa) { flag = 1; dfs(v[i], cur); dp[cur] += min(w[i], dp[v[i]]); } if(flag == 0) dp[cur] = INF;}//这种flag判断错误，求解//void dfs(int u,int fa)//{// printf("*%d*",u,dp[1]);// int i,flag=0;// dp[u]=0;// for( i=first[u]; i != -1; i = next[i])// {// flag=1;// int vv=v[i];// int ww=w[i];// if(vv==fa)// {// flag=0;// continue;// }// dfs(vv,u);// printf("&%d& ",vv);// dp[u]+=min(ww,dp[vv]);// //printf("$%d %d %d$",tmp,ww,dp[vv]);// }// if(flag==0)// dp[u]=INF;// printf("%d\n",dp[u]);////}int main(){ int n,r,a,b,c; while(scanf("%d%d",&n,&r)!=EOF) { if(n==0 && r==0) break; memset(adj,-1,sizeof(adj)); for(int i=1; i
栈溢出的代码：
#include#include #include using namespace std;#define N 2005#define INF 0x7fffffffstruct node{ int v; int w;};vector adj[N];int dp[N];int tmp=0;void dfs(int u,int fa){ //printf("*%d*",u,dp[1]); int flag=0; dp[u]=0; for(int i=0; i
转载地址：http://crddi.baihongyu.com/