BZOJ 1596: [Usaco2008 Jan]电话网络

Description

Farmer John决定为他的所有奶牛都配备手机，以此鼓励她们互相交流。不过，为此FJ必须在奶牛们居住的N(1 <= N <= 10,000)块草地中选一些建上无线电通讯塔，来保证任意两块草地间都存在手机信号。所有的N块草地按1..N 顺次编号。所有草地中只有N-1对是相邻的，不过对任意两块草地A和B(1 <= A <= N; 1 <= B <= N; A != B)，都可以找到一个以A开头以B结尾的草地序列，并且序列中相邻的编号所代表的草地相邻。无线电通讯塔只能建在草地上，一座塔的服务范围为它所在的那块草地，以及与那块草地相邻的所有草地。请你帮FJ计算一下，为了建立能覆盖到所有草地的通信系统，他最少要建多少座无线电通讯塔。

Input

* 第1行: 1个整数，N

* 第2..N行: 每行为2个用空格隔开的整数A、B，为两块相邻草地的编号

Output

* 第1行: 输出1个整数，即FJ最少建立无线电通讯塔的数目

题解：

定义。
dp[i][0] = sum(min(dp[s][2],dp[s][1]))自己没被选，父节点被选中
dp[i][1] = sum(min(dp[s][1],dp[s][2]))自己没被选，某儿子结点被选中
dp[i][2] = sum(min(dp[s][0],dp[s][1],dp[s][2]))自己被选中
求dp[i][1] 时需注意当所有的dp[s][1] < dp[s][2]时是不满足条件的。

ans=min(dp[1][2],dp[1][1])

代码：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

//by zrt

//problem:

using namespace std;

typedef long long LL;

const int inf(0x3f3f3f3f);

const double eps(1e-9);

int n;

int H[10005],X[20005],P[20005],tot;

inline void add(int x,int y){

    P[++tot]=y;X[tot]=H[x];H[x]=tot;

}

int dp[10005][3];//0 not 1 yes

void dfs(int x,int fa){

    dp[x][0]=0;

    dp[x][2]=1;

    dp[x][1]=0;

    int stot=0;

    bool flag=0;

    int minn=inf;

    for(int i=H[x];i;i=X[i]){

        if(fa!=P[i]){

            stot++;

            dfs(P[i],x);

            dp[x][2]+=min(dp[P[i]][0],min(dp[P[i]][1],dp[P[i]][2]));

            dp[x][0]+=min(dp[P[i]][2],dp[P[i]][1]);

            if(dp[P[i]][1]<dp[P[i]][2]){

                dp[x][1]+=dp[P[i]][1];

                if(minn>dp[P[i]][2]-dp[P[i]][1]){

                    minn=dp[P[i]][2]-dp[P[i]][1];

                }

            }else {

                flag=1;

                dp[x][1]+=dp[P[i]][2];

            }

        }

    }

    if(stot==0){

        dp[x][1]=inf;

        return;

    }

    if(!flag){

        dp[x][1]+=minn;

    }

}

int main(){

    #ifdef LOCAL

    freopen("in.txt","r",stdin);

    freopen("out.txt","w",stdout);

    #endif

    scanf("%d",&n);

    for(int i=1,x,y;i<n;i++){

        scanf("%d%d",&x,&y);

        add(x,y);

        add(y,x);

    }

    dfs(1,-1);

    printf("%d\n",min(dp[1][2],dp[1][1]));

    return 0;

}

巴特西

BZOJ 1596: [Usaco2008 Jan]电话网络

Description

Input

Output

最新文章

热门文章