HDU 6178 Monkeys（树上的二分匹配）-白红宇

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

阅读量：4948 次

发布时间：2019-06-11

本文共 2277 字，大约阅读时间需要 7 分钟。

题意：

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

思路：

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

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

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

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 #include
            
              9 #include
              10 #include
              
                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 == '\n' || ch == '\r' || ch == '\t'; 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\n",(k+1)/2);101 else printf("%d\n",ans+k-2*ans);102 }103 return 0;104 }

转载于:https://www.cnblogs.com/zyb993963526/p/7426342.html

你可能感兴趣的文章