「BZOJ1596」[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最少建立无线电通讯塔的数目
Sample Input
5
1 3
5 2
4 3
3 5
输入说明:
Farmer John的农场中有5块草地：草地1和草地3相邻，草地5和草地2、草地
4和草地3，草地3和草地5也是如此。更形象一些，草地间的位置关系大体如下：
（或是其他类似的形状）
4 2
| |
1–3–5
1 3
5 2
4 3
3 5
输入说明:
Farmer John的农场中有5块草地：草地1和草地3相邻，草地5和草地2、草地
4和草地3，草地3和草地5也是如此。更形象一些，草地间的位置关系大体如下：
（或是其他类似的形状）
4 2
| |
1–3–5
Sample Output
2
输出说明:
FJ可以选择在草地2和草地3，或是草地3和草地5上建通讯塔。
题解
搞了半天树形dp发现可以贪心
f[i][0]：以i为根的子树中所有点均被覆盖且草地i上无信号塔所需的最小塔数（i被其儿子覆盖）
f[i][1]：以i为根的子树中所有点均被覆盖且草地i上有信号塔所需的最小塔数
f[i][2]：以i为根的子树中除i点以外其余点均被覆盖所需的最小塔数
大概这样。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 100000000 #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt; int head[10005],f[3][10005]; struct data{int to,next;}e[20005]; inline void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; } void dp(int x,int fa) { int sum=0; f[1][x]=1;f[0][x]=inf; for(int i=head[x];i;i=e[i].next) { if(e[i].to==fa)continue; dp(e[i].to,x); f[1][x]+=min(f[0][e[i].to],min(f[1][e[i].to],f[2][e[i].to])); f[2][x]+=f[0][e[i].to]; sum+=min(f[0][e[i].to],f[1][e[i].to]); } for(int i=head[x];i;i=e[i].next) { if(e[i].to==fa)continue; f[0][x]=min(f[0][x],f[1][e[i].to]+sum-min(f[0][e[i].to],f[1][e[i].to])); } } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); insert(v,u); } dp(1,0); printf("%d",min(f[0][1],f[1][1])); return 0; } |
贪心遍历每个点，如果它的孩子都没有真正覆盖的，同时他自己和他父亲都没有真正覆盖的，就把它的父亲覆盖，答案加一。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> #include<cmath> #define inf 0x7fffffff #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,cnt,ans; int head[10005]; bool mark[10005]; struct data{int to,next;}e[20005]; inline void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; } void getans(int x,int fa) { bool flag=0; for(int i=head[x];i;i=e[i].next) { if(e[i].to==fa)continue; getans(e[i].to,x); if(mark[e[i].to])flag=1; } if(!flag&&!mark[x]&&!mark[fa]){ans++;mark[fa]=1;} } int main() { n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(); insert(u,v); insert(v,u); } getans(1,0); printf("%d",ans); return 0; } |
Subscribe
计数器 9854143
OI 课件=>
OI 课件=>