题解 P6857 【梦中梦与不再有梦】

InformationEntropy · 2020-10-21 23:36:08 · 题解

本题的实质就是求有 n 个顶点的无向完全图能够一笔画的最多边数。

当一个无向图有 0 个或 2 个奇点（度为奇数的点），那么它就是一个欧拉图，可以一笔画完所有的边。

考虑到 n 为奇数时，每个顶点的度都为偶数，有 0 个奇点，故一定为欧拉图，所以最多边数就是总边数，即 \dfrac {n\times (n-1)}{2}。

当 n 为偶数时，考虑删掉一些边使它变为一个欧拉图。由于每个点的度都为奇数，故有 n 个奇点，而边双向连通，所以每删除一条边最多可减少两个奇点，我们需要把奇点减少至 2 个，所以至少要删 \dfrac {n-2}{2} 条边，最终边数为 \dfrac{n\times (n-1)}{2}-\dfrac{n-2}{2}。

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef double db;
template<class T>inline void read(T &x)
{//快读
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    x *= f;
}
int main()
{
    ll t, n;//不开 long long 见祖宗
    read(t);
    for (int i = 1; i <= t; i++)
    {
        read(n);
        if (n == 0 || n == 1)
        {
            cout << 0 << '\n';//注意特判
        } else if (n == 2) {
            cout << 1 << '\n';
        } else if (n % 2 == 1) {
            cout << n*(n - 1) / 2 << '\n';
        } else {
            cout << n*(n - 1) / 2 - n / 2 + 1 << '\n';
        }
    }
    return 0;
}