JZOJ5455 拆网线

Description

　　企鹅国的网吧们之间由网线互相连接，形成一棵树的结构。现在由于冬天到了，供暖部门缺少燃料，于是他们决定去拆一些网线来做燃料。但是现在有K只企鹅要上网和别人联机游戏，所以他们需要把这K只企鹅安排到不同的机房（两只企鹅在同一个机房会吵架），然后拆掉一些网线，但是需要保证每只企鹅至少还能通过留下来的网线和至少另一只企鹅联机游戏。
　　所以他们想知道，最少需要保留多少根网线？

Input

　　第一行一个整数T，表示数据组数；
　　每组数据第一行两个整数N，K，表示总共的机房数目和企鹅数目。
　　第二行N-1个整数，第i个整数Ai表示机房i+1和机房Ai有一根网线连接(1≤Ai≤i)。

Output

　　每组数据输出一个整数表示最少保留的网线数目。

Sample Input

Sample Output

　　2
　　2

Data Constraint

　　对于30%的数据：N≤15；
　　对于50%的数据：N≤300；
　　对于70%的数据：N≤2000；
　　对于100%的数据：2≤K≤N≤100000，T≤10。

Solution

　　首先算出这棵树中最多有多少一条网线连接两个机房，且这两个机房没有其他网线与之相连，这个可以用拓扑或者dfs序处理，那么这些机房之外的机房就只能一根网线联通一个机房。

 1 #include <cstdio>
 2 using namespace std;
 3 struct arr 
 4 { 
 5     int x,y,next;
 6 };
 7 arr edge[200000];
 8 int ls[200000],n,m,tin,t,d[200000],fa[200000];
 9 bool f[200000];
10 int ss(int x)
11 {
12     f[x]=false;
13     int i=ls[x];
14     while (i!=0)
15     {
16         int ii=edge[i].y;
17         if (f[ii])
18         {
19             fa[ii]=x;
20             ss(ii);
21         }
22         i=edge[i].next;
23     }
24     if (d[x]==0)
25         d[fa[x]]++;
26     else 
27         if (x!=1) tin--;
28     if (d[x]>1) tin=tin-d[x]+1;
29 }
30 int main()
31 {
32     scanf("%d",&t);
33     for (int i=1;i<=t;i++)
34     {
35         scanf("%d%d",&n,&m);    
36         for (int j=1;j<=n;j++)
37         {
38             f[j]=true;    
39             fa[j]=0;
40             d[j]=0;
41         }
42         for (int j=1;j<=n-1;j++)
43         {
44             int x;
45             scanf("%d",&x);
46             edge[j*2-1].x=j+1;
47             edge[j*2-1].y=x;
48                edge[j*2-1].next=ls[edge[j*2-1].x];
49             ls[edge[j*2-1].x]=j*2-1;
50             edge[j*2].x=x;
51             edge[j*2].y=j+1;
52             edge[j*2].next=ls[edge[j*2].x];
53             ls[edge[j*2].x]=j*2;
54         }
55         tin=n-1;
56          ss(1);
57          if (tin*2>=m)
58          {
59              if (m%2==0) printf("%d
",m/2);
60             else printf("%d
",m/2+1);
61         }
62          else
63              printf("%d
",tin+(m-tin*2));
64         for (int j=1;j<=n*2;j++)
65         {
66             edge[j].x=0;edge[j].y=0;
67             edge[j].next=0;ls[j]=0;
68         }
69     }
70 }

View Code