首页 > 代码库 > POJ 1947 Rebuilding Roads

POJ 1947 Rebuilding Roads

2024-07-14 20:01:55   218人阅读

　　题目意思：有N 个节点形成树状结构，现在想知道。给定一个人P删除最少的边使得形成一个子树子树的节点有P 个节点；

很明显的树形DP[i][j] I为根子树形成j个节点最少减多少；

　　依赖性01问题，只不过这个合并时候的输的初始化不好想；

给出代码加注释；

#include <cstdio>#include <algorithm>#include <cmath>#include <cstdlib>#include <cstring>using namespace std;const int maxn=155;const int INF=0x3fffffff;struct Edge{    int to,dis,pre;    Edge(int to=0,int dis=0,int pre=0):to(to),dis(dis),pre(pre){}};Edge edge[maxn];int head[maxn],pos;int dp[maxn][maxn];int N,P;bool fa[maxn];void inint(){    memset(fa,false,sizeof(fa));    for(int i=1;i<maxn;i++)        for(int j=1;j<maxn;j++)            dp[i][j]=INF;    memset(head,-1,sizeof(head));    pos=0;}void add_edge(int s,int to,int dis){    edge[pos]=Edge(to,dis,head[s]);    head[s]=pos++;}int dfs(int s){    int ans=1,key;    dp[s][1]=0;//一开始只有一个跟节点；    for(int w=head[s];~w;w=edge[w].pre)    {        Edge & tmp=edge[w];        key=dfs(tmp.to);        ans+=key;        for(int i=ans;i>=1;i--)        {            dp[s][i]++;  //多引出一个分支所以对应原本的【s】【i】，要切除新枚举出来的子树；            for(int j=1;j<=key&&(j<i);j++)                dp[s][i]=min(dp[s][i],dp[s][i-j]+dp[tmp.to][j]);        }    }    return ans;}void solve(){    int root;    for(int i=1;i<=N;i++)    if(!fa[i]){root=i;break;}    dfs(root);    int ans=dp[root][P];    for(int i=1;i<=N;i++)        ans=min(ans,dp[i][P]+1);//之所以加一 因为不是跟所以要把他和父亲的连线切了    printf("%d\n",ans);}int main(){    int a,b;    while(~scanf("%d%d",&N,&P))    {        inint();        for(int i=2;i<=N;i++)        {            scanf("%d%d",&a,&b);            add_edge(a,b,-1);            fa[b]=true;        }       solve();    }}

 


联系
我们