JZOJ 5455 拆网线
2024-09-06 12:50:54
Time Limits: 1000 ms Memory Limits: 65536 KB Detailed Limits
Description
企鹅国的网吧们之间由网线互相连接,形成一棵树的结构。现在由于冬天到了,供暖部门缺少燃料,于是他们决定去拆一些网线来做燃料。但是现在有K只企鹅要上网和别人联机游戏,所以他们需要把这K只企鹅安排到不同的机房(两只企鹅在同一个机房会吵架),然后拆掉一些网线,但是需要保证每只企鹅至少还能通过留下来的网线和至少另一只企鹅联机游戏。
所以他们想知道,最少需要保留多少根网线?
Input
第一行一个整数T,表示数据组数;
每组数据第一行两个整数N,K,表示总共的机房数目和企鹅数目。
第二行N-1个整数,第i个整数Ai表示机房i+1和机房Ai有一根网线连接(1≤Ai≤i)。
Output
每组数据输出一个整数表示最少保留的网线数目。
Sample Input
2
4 4
1 2 3
4 3
1 1 1
Sample Output
2
2
Data Constraint
对于30%的数据:N≤15;
对于50%的数据:N≤300;
对于70%的数据:N≤2000;
对于100%的数据:2≤K≤N≤100000,T≤10。
解题思路
本来和GhostCai神犇吐槽这道题,结果yy出了正解233。。首先要让他们两个两个配对一定比一坨优,所以问题转换成了先求出一个最大匹配,用n-最大独立集求,最大独立集直接dp。然后在分类讨论企鹅的数量,如果数量大于这个匹配,就说明剩下的企鹅只能抱团,再加一个K-最大匹配*2。如果数量小于这个匹配,就说明所有企鹅可以两个两个配对。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const int MAXN = 100005;
inline int rd(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int n,T,K,ans;
int head[MAXN],cnt;
int to[MAXN<<1],nxt[MAXN<<1];
int dp[MAXN][3];
inline void add(int bg,int ed){
to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}
inline void dfs(int x,int fa){
dp[x][1]=1;
for(register int i=head[x];i;i=nxt[i]){
int u=to[i];
if(u==fa) continue;
dfs(u,x);
dp[x][1]+=dp[u][0];
dp[x][0]+=max(dp[u][0],dp[u][1]);
}
}
int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
T=rd();
while(T--){
ans=0;memset(dp,0,sizeof(dp));
cnt=0;memset(head,0,sizeof(head));
n=rd();K=rd();
for(register int i=1;i<n;i++){
int x=rd();
add(x,i+1);add(i+1,x);
}
dfs(1,0);
ans=n-max(dp[1][0],dp[1][1]);
if(ans*2>=K) cout<<(K+1)/2<<endl;
else cout<<K-ans<<endl;
}
return 0;
}
最新文章
- 【总结2】PhpStorm利用XDebug调试PHP技巧
- 坑爹的私有API
- Objective-C数据类型之id,SEL,BOOL,nil,NULL和NSNull
- UML学习总结
- Timeout expired超时时间已到. 达到了最大池大小 错误及Max Pool Size设置
- sass中出现的中文问题
- dorado需要的包
- Android SharedPreferences登录记住密码
- 保护DNS服务器3大方法
- Android中TextView中内容不换行的解决方法
- 编码规范系列(二):Eclipse Checkstyle配置
- java学习——java中的反射学习笔记
- Linux命令之rz命令与sz命令
- ubuntu下git clone 提速
- asp.net --- reponse对象写图片
- ubuntu16.04编译安装opencv3.4.6
- Android源码目录结构详解
- Vim编程常用命令
- Python学习札记(二十二) 函数式编程3 filter &; SyntaxError: unexpected EOF while parsing
- android AndroidManifest.xml uses-feature 详解