【NOIP2017提高A组冲刺11.6】拆网线
2024-08-29 23:37:17
和syq大兄弟吐槽题目不小心yy出了正解..
最优的选法就是选两个两个相互独立的,欸这不就是最大匹配吗?那多的企鹅就新加一条边呗?不够的就除以2上取整呗?
欸?AC了?
树也是一个二分图,最大匹配=最小点覆盖=N-最大独立集,树上的最大独立集就是没有上司的舞会,没了。
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; inline int rd(){
int ret=,f=;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-:;
while(isdigit(c))ret=ret*+c-'',c=getchar();
return ret*f;
} const int MAXN=; struct Edge{
int next,to;
}e[MAXN<<];
int ecnt,head[MAXN];
inline void add(int x,int y){
e[++ecnt].next = head[x];
e[ecnt].to = y;
head[x] = ecnt;
} int n,m,T; int f[MAXN][]; void dfs(int x,int pre){
f[x][]=;
for(int i=head[x];i;i=e[i].next){
int v=e[i].to;
if(v==pre) continue;
dfs(v,x);
f[x][]+=f[v][];
f[x][]+=max(f[v][],f[v][]);
}
} void solve(){
memset(f,,sizeof(f));
memset(head,,sizeof(head));
ecnt=;
n=rd();m=rd();
for(int i=;i<=n;i++){
int x=rd();
add(i,x);add(x,i);
}
dfs(,);
int ans=n-max(f[][],f[][]);
if(ans*>=m) cout<<(m+)/<<endl;
else cout<<ans+(m-ans*)<<endl;
} int main(){
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
T=rd();
while(T--) solve();
return ;
}
最新文章
- 黑马----JAVA迭代器详解
- IOS推荐学习网站
- 在实体注解OneToMany时,要加上mappedby,避免产生中间表。
- Normalize [ 浏览器渲染格式化 ]
- C#_delegate - Pair<;T>; &; 简单顺序逆序 &; 方法委托(在Pair类下)&;枚举类型 混搭使用
- Android(java)学习笔记137:Android中SimpleAdapter,ArrayAdapter和BaseAdapter常见的适配器
- 配置WifiConfiguration
- OC基础:block.字面量
- linux 命令后台执行
- HDU 5730 - Shell Necklace
- poj3673---双重for循环
- 转 ORACLE数据库它可以存储 中文 字节或字符
- win10 运行sqlplus报错“SP2-1503: 无法初始化 Oracle 调用界面”
- 编译安装 apache 2.4.6
- linux新手记录;可执行文件直接运行
- JS数组遍历
- MT【272】更大的视野,更好的思路.
- 3.建造者模式(Builder)
- iptables精通
- Go内置库模块 flag