hdu 3452

Bonsai

题目描述： 给你一个无向树，每个边都有一个权值，要求删除一些边，保证叶子节点不存在到根节点的路径。

// 汗死，用l邻接表一直wa,  后来想想规模不大，直接就用数组做了

// dp[i] =min{t[i][j],dp(j)} （t[i][j] ，i 为根，j为i下一个结点）

代码：

#include<iostream> #include <algorithm> using namespace std; #include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> const int MAX=1000; int t[MAX+5][MAX+5]; const int inf=2000000; bool used[MAX+5]; int n,root; inline int min(int a,int b){return a>b? b:a;} int dp(int r) { // t[i][j] ，i 为根，j为i下一个结点 // dp[i] =min{t[i][j],dp(j)} used[r]=true; int ans=0; bool tt=false; for(int i=1;i<=n;i++) { if(!used[i]&&t[r][i]<inf) { tt=true; ans+=min(dp(i),t[r][i]); } } if(tt) return ans; return inf; } int main() { // freopen("1.in","r",stdin); while(scanf("%d %d",&n,&root)!=EOF) { if(n==0&&root==0) break; int s,e,w; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) t[i][j]=inf; } for(int i=1;i<n;i++) { scanf("%d %d %d",&s,&e,&w); t[s][e]=t[e][s]=w; } if(n<=1) {printf("0/n");continue;} memset(used,false,sizeof(used)); cout<<dp(root)<<endl; } return 1; }

刚刚又写了邻接表版本的，重新写，却过了...一块贴出来

#include<iostream> #include <algorithm> using namespace std; #include <cstdlib> #include <cstdio> #include <cstring> #include <cmath> const int MAX=1000; const int inf=2000000; bool used[MAX+5]; int n,root; typedef struct Node { int e,w; Node *next; }node; node t[MAX+5]; void build(int s,int e,int w) { node *d=t+s; node *u=new node; u->e=e,u->w=w; u->next=d->next; d->next=u; } inline int min(int a,int b){return a>b? b:a;} int dp(int r) { node *tt=r+t; node yy; used[r]=true; int ans=0; bool flag=false; while(tt->next) { tt=tt->next; if(!used[tt->e]) { flag=true; ans+=min(tt->w,dp(tt->e)); } } if(flag) return ans; return inf; } int main() { //freopen("1.in","r",stdin); while(scanf("%d %d",&n,&root)!=EOF) { if(n==0&&root==0) break; int s,e,w; for(int i=1;i<=n;i++) t[i].next=NULL; memset(used,false,sizeof(used)); for(int i=1;i<n;i++) { scanf("%d %d %d",&s,&e,&w); build(s,e,w); build(e,s,w); } if(n<=1) {printf("0/n");continue;} int ans=dp(root); cout<<ans<<endl; } return 1; }