bzoj1907: 树的路径覆盖（树形DP）

　　一眼题...

　　f[i][0]表示在i连接一个子树的最小值，f[i][1]表示在i连接两个子树的最小值，随便转移...

　　样例挺强的1A了美滋滋...

UPD：学习了2314的写法之后短了好多T T

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=, inf=1e9;

struct poi{int too, pre;}e[maxn];

int n, T, tot, x, y;

int f[maxn][], last[maxn];

void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}

inline int min(int a, int b){return a<b?a:b;}

void dfs(int x, int fa)

{

    f[x][]=maxn; f[x][]=; int sum=;

    for(int i=last[x], too;i;i=e[i].pre)

    if((too=e[i].too)!=fa)

    {

        dfs(too, x);

        f[x][]=min(f[x][]+min(f[too][], f[too][]), f[x][]+f[too][]-);

        f[x][]=min(f[x][]+min(f[too][], f[too][]), sum+f[too][]);

        sum+=min(f[too][], f[too][]);

    }

}

int main()

{

    read(T);

    while(T--)

    {

        read(n); memset(last, , (n+)<<); tot=;

        for(int i=;i<n;i++) read(x), read(y), add(x, y), add(y, x);

        dfs(, ); printf("%d\n", min(f[][], f[][]));

    }

}

旧代码：

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=, inf=1e9;

struct poi{int too, pre;}e[maxn];

int n, T, tot, x, y;

int f[maxn][], last[maxn];

void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', c=getchar();

    k*=f;

}

inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;}

inline int min(int a, int b){return a<b?a:b;}

void dfs(int x, int fa)

{

    int mn1=inf, mn2=inf, mni1=, mni2=, tmp=; f[x][]=; f[x][]=-;

    for(int i=last[x], too;i;i=e[i].pre)

    if((too=e[i].too)!=fa)

    {

        dfs(too, x);

        f[x][]+=min(f[too][], f[too][]);

        if(f[too][]==min(f[too][], f[too][])) tmp=;

        if(f[too][]-min(f[too][], f[too][])<mn1) mn1=f[too][]-min(f[too][], f[too][]), mni1=too;

        else if(f[too][]-min(f[too][], f[too][])<mn2) mn2=f[too][]-min(f[too][], f[too][]), mni2=too;

    }

    f[x][]+=tmp;

    if(!(f[x][]-tmp)) {f[x][]=; f[x][]=inf; return;}

    if(mn2==inf) {f[x][]=inf; return;}

    for(int i=last[x], too;i;i=e[i].pre)

    if((too=e[i].too)!=fa)

    {

        if(too==mni1 || too==mni2) f[x][]+=f[too][];

            else f[x][]+=min(f[too][], f[too][]);

    }

}

int main()

{

    read(T);

    while(T--)

    {

        read(n); memset(last, , (n+)<<); tot=;

        for(int i=;i<n;i++) read(x), read(y), add(x, y), add(y, x);

        dfs(, ); printf("%d\n", min(f[][], f[][]));

    }

}

巴特西

bzoj1907: 树的路径覆盖（树形DP）

最新文章

热门文章