HDU 6178 Monkeys(树上的二分匹配)

时间:2023-12-24 10:46:01

http://acm.hdu.edu.cn/showproblem.php?pid=6178

题意:
现在有一n个顶点的树形图,还有k只猴子,每个顶点只能容纳一只猴子,而且每只猴子至少和另外一只猴子通过边相连,现在要删边,保留最少的边使得满足题意。

思路:

贪心的想一想,顶点两两匹配时一条边的贡献值就是两只猴子,那这不就是二分匹配吗。所以先求个二分匹配即可,然后如果此时还是不够的话,那么剩下的猴子每只猴子都需要一条边。

如果用二分匹配的算法可能不太行,虽然看别人用Hopcroft-Carp算法跑了998ms惊险过了,不过我当时也用了Hopcroft-Carp算法。。但结果无限TLE。。。

因为模型是树,所以直接dfs求最大匹配或者树形dp求即可。

 #include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn=+; int n, k;
int tot;
int ans;
int head[maxn]; struct node
{
int v,next;
}e[maxn*]; namespace fastIO {
#define BUF_SIZE 1000000
//fread -> read
bool IOerror = ;
inline char nc() {
static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
if(p1 == pend) {
p1 = buf;
pend = buf + fread(buf, , BUF_SIZE, stdin);
if(pend == p1) {
IOerror = ;
return -;
}
}
return *p1++;
}
inline bool blank(char ch) {
return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
}
inline void read(int &x) {
char ch;
while(blank(ch = nc()));
if(IOerror)
return;
for(x = ch - ''; (ch = nc()) >= '' && ch <= ''; x = x * + ch - '');
}
#undef BUF_SIZE
};
using namespace fastIO; bool used[maxn]; void addEdge(int u, int v)
{
e[tot].v=v;
e[tot].next=head[u];
head[u]=tot++;
} void dfs(int u, int fa)
{
int cnt=,us=;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].v;
if(v==fa) continue;
dfs(v,u);
cnt++; //有多少个直接相连的子节点
us+=used[v]; //直接相连的子节点中有多少个已经被使用
}
if(cnt-us>=) ans++,used[u]=true;
} int main()
{
//freopen("in.txt","r",stdin);
int T;
read(T);
while(T--)
{
tot=;
memset(head,-,sizeof(head));
read(n);
read(k);
for(int i=;i<=n;i++)
{
int x;
read(x);
addEdge(x,i);
addEdge(i,x);
}
ans=;
memset(used,false,sizeof(used));
dfs(,-);
if(*ans>=k) printf("%d\n",(k+)/);
else printf("%d\n",ans+k-*ans);
}
return ;
}