最近都在做dp相关呀…

hdu 1520 树的最大独立集

题意：给出一棵树， 每个节点有权值，要求父节点和子节点不能同时取，求能够取得的最大值。

思路：把树用有向边存下来。

dp(i)(0):不选i点子树能够得到的最大价值;dp(i)(1):选i点子树能够得到的最大价值。

dp(i)(0)=sum(max(dp(k)(0),dp(k)(1)));//子节点可选可不选
dp(i)(1)=sum(dp(k)(0));//子节点都不选

从可能为根的节点开始dfs，先得到树叶的dp值，然后往上回溯得到根的dp值，取最大值即为答案。

完整代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
vector<int>v[6010];
bool nr[6010];//true:不是根结点
int dp[6010][2];//dp[i][0]:不选i点子树能够得到的最大价值
void dfs(int id)
{
    for(int i=0;i<v[id].size();i++)
    {
        int temp=v[id][i];
        dfs(temp);
        dp[id][0]+=max(dp[temp][0],dp[temp][1]);//子节点可选可不选
        dp[id][1]+=dp[temp][0];//子节点都不选
    }
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(nr,0,sizeof(nr));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&dp[i][1]);
            dp[i][0]=0;
            v[i].clear();
        }
        int x,y;
        while(scanf("%d%d",&x,&y)!=EOF)
        {
            if(x==0&&y==0)break;
            v[y].push_back(x);
            nr[x]=true;
        }
        int ans=-1;
        for(int i=1;i<=n;i++)
        {
            if(!nr[i])
            {
                dfs(i);
                ans=max(ans,max(dp[i][0],dp[i][1]));
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

poj 1655 树的重心

题意：一颗n结点无根树，选择一个结点为根，将无根树->有根树，最大子树的结点数最小，我们称该节点为质心（树的重心），求树的重心，如果有多个，按照节点编号升序输出。

思路：

完整代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define MOD 100000000
#define INF 0x3f3f3f3f
using namespace std;
int top,n;
int head[20010];
int num[20010];//每个节点的子树的节点数（包括自己）
int dp[20010];//删除节点i后最大联通块的节点数
//dp[i]=max(dp[j](j为i的子节点),n-dp[i](i上方子树))
struct edge
{
    int to;
    int next;
}eg[20010*2];
void add(int a,int b)
{
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
void dfs(int id,int fa)
{
    //printf("%d %d\n",id,fa);
    int mmax=-1;//id的子节点中最大的联通块
    num[id]=1;
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        if(eg[i].to!=fa)
        {
            dfs(eg[i].to,id);
            num[id]+=num[eg[i].to];
            mmax=max(mmax,num[eg[i].to]);
        }
    }
    dp[id]=max(mmax,n-num[id]);
    //printf("id:%d num:%d dp:%d\n",id,num[id],dp[id]);
}
int main()
{
    int m;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d",&n);
        memset(head,-1,sizeof(head));
        top=0;
        for(int i=0;i<n-1;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            add(x,y);
            add(y,x);
        }
        /*for(int j=1;j<=n;j++)
        {
            for(int i=head[j];i!=-1;i=eg[i].next)
                printf("%d ",eg[i].to);
            printf("\n");
        }*/
        dfs(1,1);//求出每个节点的子树的节点数（包括自己）
        int pos=1;
        for(int i=1;i<=n;i++)
        {
            if(dp[i]<dp[pos])
                pos=i;
        }
        printf("%d %d\n",pos,dp[pos]);
    }
    return 0;
}

poj 2631 树的直径

题意：树上最长的简单路径即为树的直径，求树的直径。

思路：

两种方法。

1⃣两次dfs(bfs)：先任选一个起点BFS找到最长路的终点，再从终点进行BFS，则第二次BFS找到的最长路即为树的直径。

完整代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define MOD 100000000
#define INF 0x3f3f3f3f
using namespace std;
int top,pos,mmax;
int head[10010];
struct edge
{
    int to;
    int cost;
    int next;
}eg[2*10010];
void add(int a,int b,int c)
{
    eg[top].cost=c;
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
void dfs(int id,int fa,int v)
{
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        if(eg[i].to!=fa)
        {
            dfs(eg[i].to,id,v+eg[i].cost);
        }
    }
    if(v>mmax)
    {
        mmax=v;
        pos=id;
    }
}
int main()
{
    int x,y,z;
    top=0;
    memset(head,-1,sizeof(head));
    while(scanf("%d%d%d",&x,&y,&z)!=EOF)
    {
        add(x,y,z);
        add(y,x,z);
    }
    mmax=-1;
    dfs(1,1,0);//任选一个点，找离它最远的点
    mmax=-1;
    dfs(pos,pos,0);//从上面最远的点开始找离这个点最远的点
    printf("%d\n",mmax);
    return 0;
}

2⃣dp：对于任意一个点，搜索其两个能延伸最远和次远的儿子，把两个距离相加再加上两儿子到父亲的距离再取最大就是树的直径，而且两儿子不能在一条延伸路径上。f(i)(0),f(i)(1)分别记录以顶端端点为i的最长链和次长链长度，当子结点的最长边（次短边没有影响，因为对于i来说的两条路不能在一条延伸路径上）加上到父结点的距离大于父结点的最长边时，更新父结点的最长边和次长边。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#define MOD 100000000
#define INF 0x3f3f3f3f
using namespace std;
int top;
int head[10010];
int dp[10010][2];//顶端为i的最长链和次长链的长度
struct edge
{
    int to;
    int cost;
    int next;
}eg[2*10010];
void add(int a,int b,int c)
{
    eg[top].cost=c;
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
void dfs(int id,int fa)
{
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        if(eg[i].to!=fa)
        {
            dfs(eg[i].to,id);
            if(dp[eg[i].to][0]+eg[i].cost>dp[id][0])
            {
                dp[id][1]=dp[id][0];
                dp[id][0]=dp[eg[i].to][0]+eg[i].cost;
            }
            else if(dp[eg[i].to][0]+eg[i].cost>dp[id][1])
                dp[id][1]=dp[eg[i].to][0]+eg[i].cost;
        }
    }
}
int main()
{
    int x,y,z;
    top=0;
    memset(head,-1,sizeof(head));
    memset(dp,0,sizeof(dp));
    while(scanf("%d%d%d",&x,&y,&z)!=EOF)
    {
        //if(x==0&&y==0&&z==0)break;
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,1);//任选一个点，找离它最远的点和次远的点
    printf("%d\n",dp[1][0]+dp[1][1]);
    return 0;
}