BZOJ 5060 魔方国

2017.10.23

题目大意

给你一个N个点的无向图，让你加入M条边，之后设置一些点为特殊点，每个特殊点能够辐射与其距离不超过K条边的点，求最小的放置个数的可能值。

这题本来觉得好难啊……但是仔细思考之后发现一个事情：最小的方案就是一个菊花图，最多的方案就是所有边都连接前两个点，之后所有点都不连边。之后就非常简单了。直接暴力构图解决就好了。

但是WA得很惨……后来看了dalao的代码才发现我这特判不够啊……

  1. K=0.此时特殊点只能覆盖自己，此时maxN=minN=n.
  2. M=0.此时没有边可以加进去，此时maxN=minN=n.
  3. N=1,M!=0.此时没有办法加边（要求两个不同点之间连边），此时无方案，输出0.
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,k;
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    if(n==1&&m) {printf("0\n");return 0;}
    if(!k||!m) {printf("1\n%d",n);return 0;}
    if(n-1<=m)
    {
        printf("%d\n",n-1);
        for(int i=1;i<n-1;++i) printf("%d ",i);
        printf("%d",n-1);
    }
    else
    {
        printf("%d\n",m);
        for(int i=n-m;i<n-1;++i) printf("%d ",i);
        printf("%d",n-1);
    }
    return 0;
}