首页 > 代码库 > BZOJ 1596: [Usaco2008 Jan]电话网络
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 yesvoid 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]电话网络
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。