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

· · 题解

· 题意

由题面中：

每两个梦之间都有且仅有一条桥梁直接相连，不会有桥梁从一个梦连向自身。

只能被经过一次，无论是正向经过还是反向经过。

到达一个梦且与它相连的所有桥梁都不能经过

可知，题意是让我们删除掉最少的边，使得图中存在欧拉路。

欧拉路的定义：

存在这样一种图，可以从其中一点出发，不重复地走完其所有的边。

如果欧拉路的起点与终点相同，则称之为欧拉回路。

显而易见，欧拉路存在的充要条件如下：

①图是连通的，若不连通不可能一次性遍历所有边。

②对于无向图：有且仅有两个点，与其相连的边数为奇数，其他点相连边数皆为偶数；或所有点皆为偶数边点。对于两个奇数点，一个为起点，一个为终点。起点需要出去，终点需要进入，故其必然与奇数个边相连。

如果存在这样一个欧拉路，其所有的点相连边数都为偶数，那说明它是欧拉回路。

因为此时它的起点即是终点，出去后还会回来，刚好形成偶数边。

③对于有向图：除去起点和终点，所有点的出度与入度相等。起点出度比入度大1，终点入度比出度大1。若起点终点出入度也相同，则为欧拉回路。

欧拉路问题也常被称为一笔画问题。

——以上摘自【朝夕的ACM笔记】图论-欧拉路

· 解题思路 & 方法

其实前面的dalao们已经说得很清楚了，这位大佬写得很好懂 （连我都懂了） ，我就不赘述了（其实是懒+怕说不好qwq）

· Code

#include <iostream>
#define ll long long
using namespace std;
ll t,n;//不开long long见祖宗（
int main(){
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n;
        if(n%2)
            cout<<n*(n-1)/2<<endl;
        else
            cout<<n*(n-1)/2-(n-2)/2<<endl;
    }
    return 0;
}