题解

A (Standard IO)

Time Limits: 1000 ms  Memory Limits: 524288 KB  Detailed Limits  

Description

帝国时代3是一款十分刺激的RTS游戏。你需要控制自己的一块殖民地，发展殖民地的经济和军事，最终打败其他殖民地。小L是这个游戏的狂热爱好者。一次小L打算打AI试试身手。

小L发展了几分钟，自己的殖民地人口便突破了30，然而小L发现大事不好了：

小L还处在不能建造军事单位的“发现时代”，然而敌人早已经到了“殖民时代”，发展起了一支雄厚的殖民地军，小L的殖民地受攻击了却没有一个正规的军事单位用来防御！不要认为这是小L 的技术问题，实际上AI还停留在以jg斗争为纲的落后理念上，而小L 早就以经济为第一要务了。

小L在之前已经在自己殖民地的外部，拉起了许多围墙。

帝国时代3里的围墙如图所示。

每一道围墙，总是连接着两个围墙连接处(以下简称“连接处”)。

现在小L有n个连接处，m道围墙}。

小L虽然没兵，但是他的智商比AI不知道高到那里去了，因此，只要每个连接处至少连接着k道围墙}，小L就一定能顶住这波攻击。

小L可以任意加围墙，每道围墙可以连接两个已有的连接处。

连接处是不能连接自己的，但是这里有一些规则与原帝国时代3的设定不同，两个连接处之间可以连接多个围墙，连接处初始时可能不连任何围墙，围墙之间也可以相交。

小L想知道，自己至少要多加多少道围墙}才能满足每个连接处至少连接着k道围墙？

 

Input

第一行三个整数n, m, k，表示连接处个数、围墙个数以及每个连接处至少要连接的围墙个数，连接处被编号为1到n}。

接下来m行，每行两个正整数x, y，表示这个围墙连接编号为x的连接处和编号为y的连接处。

Output

输出一行一个整数，表示至少要加的围墙的条数。

 

Sample Input

输入1： 2 0 1 输入2： 5 4 2 1 2 2 5 4 3 3 1 输入3： 4 3 2 1 2 2 3 1 2 输入4： 5 11 7 1 3 4 2 1 5 4 2 2 5 1 3 4 1 2 3 4 1 5 1 1 5

Sample Output

输出1： 1 样例1解释：初始时有两个连接处，题目中要求至少每个连接处要连1个围墙，我们加一个围墙连接这两个连接处即可。 输出2： 1 样例2解释：连接编号为5的和编号为4的连接处即可。 输出3： 2 样例3解释：编号为4的连接处没有连接任何围墙，编号为3的连接处还需要一条。连接编号为4的和编号为3的连接处之后，编号为4的连接处与另外三个连接处中任意一个连一个围墙即可，注意连接处是不能自己和自己连接的。 输出4： 7

 

Data Constraint

对于60%的数据，n × ans ≤ 10000000，ans表示最终的答案。

对于前100%的数据，n, m, k ≤ 100000，n ≥ 2, m, k ≥ 0, x ≠ y, 1 ≤ x, y ≤ n。

 

题目的大意就是给你n个点，这n个点每个点要有k条边连接到它，现在已经有了m条边，现在问你还最少需要多少边才能满足每个点至少有k条边连接到它。

我们不以边来看，以点来看。（这里有一点难以理解，但需要理解好这里，才能理解后面的内容）设f[i]表示第i个点还需要多少条边才能满足条件，sum表示所有点还需要的边的总和，在没有输入数据前，f[i]的初始值就是k，sum的初始值是n×k。

在输入x，y时，就可以对数据进行处理，以下是伪代码：

1 for(int i=1;i<=m;i++)2 {3     scanf("%lld%lld",&x,&y);4     f[x]--;5     f[y]--;6     if(f[x]>=0) sum--;7     if(f[y]>=0) sum--8;8 }

sum为需要的每个点总边数，每两个所需要的边数组合起来才是题目中所要求的一条边（这里有一点难以理解，多想一下），

定义p为至少增加的边数，那么p=sum÷2向上取整，为什么要向上取整呢？因为如果sum是奇数，那么除下来还有一个所需边数没有配对，我们又要满足条件，所以不计算这个点是不行的，故向上取整。简单来说就是如果sum是个奇数，那么就多加上1个所需边数，让所有的所需边数都有可以配对的。代码实现如下：

 

1 long long p=sum;2 if(p%2==1) p++;3 p/=2;

 

 

 

处理完这些，我们还有遍历f数组找到其中的最大值为maxn。如果maxn大于p，那么我们的符合题意（至少增加就是最少增加）的答案就是maxn。因为至少还要有maxn条边连接到数值为maxn的这个点，p又小于了maxn，那么maxn这个点就肯定没有满足条件，故应该输出的是maxn。至于为什么会出现这样的情况，可以手推一下这组数据：

    3 3 3

    1 3

    1 3

    1 3

 

综合上面的推导，就可以做出来了，附上代码：

 

#include
      
       #include
       
        #include
        
         using namespace std;long long n,m,k,maxn,sum,a,b;long long f[100005];int main(){    scanf("%lld%lld%lld",&n,&m,&k);    for(int i=1;i<=n;i++) f[i]=k;    sum=n*k;    for(int i=1;i<=m;i++)    {        scanf("%lld%lld",&a,&b);        f[a]--;        f[b]--;        if(f[a]>=0) sum--;        if(f[b]>=0) sum--;    }    for(int i=1;i<=n;i++)    if(f[i]>maxn)    maxn=f[i];    long long p=sum;    if(p%2==1) p++;    p/=2;    printf("%lld",max(maxn,p));    return 0;}
        
       
      

 

出题的大佬说：

少考虑一种情况（maxn）50；

暴力70；

向下取整90；

没开long long90；

                                                                                                                                                                                                                                                                                          by:ルオ・テンイの锦依卫

                                                                                                                                                                                                                                                                                         未经作者允许，禁止转载！