HDU 6178 Monkeys（树上的二分匹配）

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

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

思路：

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

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

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

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<cmath>
  9 #include<map>
 10 #include<set>
 11 using namespace std;
 12 typedef long long ll;
 13 const int inf = 0x3f3f3f3f;
 14 const int maxn=100000+5;
 15 
 16 int n, k;
 17 int tot;
 18 int ans;
 19 int head[maxn];
 20 
 21 struct node
 22 {
 23     int v,next;
 24 }e[maxn*2];
 25 
 26 namespace fastIO {
 27     #define BUF_SIZE 1000000
 28     //fread -> read
 29     bool IOerror = 0;
 30     inline char nc() {
 31         static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
 32         if(p1 == pend) {
 33             p1 = buf;
 34             pend = buf + fread(buf, 1, BUF_SIZE, stdin);
 35             if(pend == p1) {
 36                 IOerror = 1;
 37                 return -1;
 38             }
 39         }
 40         return *p1++;
 41     }
 42     inline bool blank(char ch) {
 43         return ch == ' ' || ch == '
' || ch == '
' || ch == '	';
 44     }
 45     inline void read(int &x) {
 46         char ch;
 47         while(blank(ch = nc()));
 48         if(IOerror)
 49             return;
 50         for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x * 10 + ch - '0');
 51     }
 52     #undef BUF_SIZE
 53 };
 54 using namespace fastIO;
 55 
 56 bool used[maxn];
 57 
 58 void addEdge(int u, int v)
 59 {
 60     e[tot].v=v;
 61     e[tot].next=head[u];
 62     head[u]=tot++;
 63 }
 64 
 65 void dfs(int u, int fa)
 66 {
 67     int cnt=0,us=0;
 68     for(int i=head[u];~i;i=e[i].next)
 69     {
 70         int v=e[i].v;
 71         if(v==fa)  continue;
 72         dfs(v,u);
 73         cnt++;  //有多少个直接相连的子节点
 74         us+=used[v]; //直接相连的子节点中有多少个已经被使用
 75     }
 76     if(cnt-us>=1)  ans++,used[u]=true;
 77 }
 78 
 79 int main()
 80 {
 81     //freopen("in.txt","r",stdin);
 82     int T;
 83     read(T);
 84     while(T--)
 85     {
 86         tot=0;
 87         memset(head,-1,sizeof(head));
 88         read(n);
 89         read(k);
 90         for(int i=2;i<=n;i++)
 91         {
 92             int x;
 93             read(x);
 94             addEdge(x,i);
 95             addEdge(i,x);
 96         }
 97         ans=0;
 98         memset(used,false,sizeof(used));
 99         dfs(1,-1);
100         if(2*ans>=k)  printf("%d
",(k+1)/2);
101         else printf("%d
",ans+k-2*ans);
102     }
103     return 0;
104 }