洛谷P1416 攻击火星

题目描述

一群外星人将要攻击火星。

火星的地图是一个n个点的无向图。这伙外星人将按照如下方法入侵，先攻击度为0的点（相当于从图中删除掉它），然后是度为1的点，依此类推直到度为n-1的点。

所有的点度统计是动态统计的。（一个点删掉后，与之相连的点的点度都会-1）。外星人攻击度为某个数的点时是同时攻击的。

你需要设计这个图的边的方案来使得未被攻击的点最多。

输入格式

输入文件包含一行一个整数n。

输出格式

一行一个整数，表示最多的最后未被攻击的点。

输入输出样例

输入 #1复制

3

输出 #1复制

1

说明/提示

【样例解释】

①-②-③，这样首先删掉度为1的①和③，此时②度数为0，不会被删去。

【数据范围】

对于20%的数据1<=n<=10

对于100%的数据1<=n<=50000

【题目来源】

tinylic改编

Solution

做完这道题，觉得自己学了14年的数学都白学了

understand

首先，你弄明白了什么是度吗？

一个点的度，等于与它连接的边的数量。

那这题怎么模拟鸭？50000点，邻接表都开不了耶……

接着，我们先从特殊到一般

special situation

当n=1时

一定会被删掉，ans=0

当n==2时，

同上n=1

当n=3时，

样例中用的是队列，ans=1

那么队列会不会是个提示呐……

当n=4时，

队列法：

也是这样最优，ans=4

但是！当n=5时，

队列法：

由于删去了两个末端节点后，中间的那个节点的度仍为2

所以它会在d=2时被删去！

有没有一种方法，可以避免这种悲剧的发生呢？

有的！

请看好了

选出两个末端节点------牺牲品

把两个末端节点与所有非末端节点相连

再把非末端节点与所有非末端节点相连

这里以n=6为例

选出两个末端节点------牺牲品

 

把两个末端节点与所有非末端节点相连

 再把非末端节点与所有非末端节点相连（并标上每个点的度）

 

肯定是两个末端节点先被删除了

但是，当它们被删除时，其他所有的节点都会被改变！

完美的错过当前的d+1

 

这，就是本题的思想：

删去一些节点后，让其他节点的度都改变为那时的d

这样“其他节点”都不会狗带咯！

general situation

当有n个点时，取其中的两个节点当牺牲品。（所以n<2时 仍有ans=0）

把两个末端节点与所有非末端节点相连

再把非末端节点与所有非末端节点相连

最终，

末端节点的度都等于n-2

非末端节点的度都等于n-1（除它本身以外全连）

那么末端节点会先被删除（d=n-2）

同时，非末端节点的度-=2 -> n-3

这时，d++（d=n-1）

非叶子节点们就安全了！

如果还是不懂，欢迎评论！

 Code

 

1 #include
     
       2 using namespace std; 3 int n; 4 int main() 5 { 6     cin>>n; 7     if(n==1) cout<<0; 8     else cout<
     

 

希望这对你有帮助！