题解：P1636 Einstein学画画

· · 题解

为什么有 7000 通过的题目的测试点是错完了的，我也很好奇呢。

下称度数为奇数的点为奇点，度数为偶数且非 0 的点为偶点。

首先我们考虑对于一个连通图最少需要几笔画完。

我们每一笔肯定会形成一个路径，这条路径的中间节点（除开头结尾的节点）会被经过两次（进一次，出一次），那么这个节点的度数就会减少 2。

考虑开头、结尾节点。如果开头、结尾节点不一样，那么会单进（或单出），这个节点的度数会减少 \bm1；如果开头、结尾节点一样，路径会形成一个环，开头、结尾贡献在同一个点上，即这个点度数减少 \bm2。

所以每次最多让两个节点的度数减少 1（路径上其余减少 2）。

那么我们此时贪心地猜想每条路径可以把两个奇点变成偶点（如果没有奇点直接删一条欧拉回路就好了，证明详见 OI-WIKI），是不是只需要操作奇点个数除以 2 次（即删完所有奇点）就什么都不剩了呢？

事实上这是正确的读者自证不难。证明：

由于图连通，所以每次一定可以找到一条连接两个奇点的路径并删除。然后图会变成一个或多个连通图，对每个连通图继续做即可。

那么删的时候可能会遇到以下情况：

  1. 如果对几对奇点操作后，在剩下的奇点中，有一个奇点与其他奇点互不连通（或整个图只有 1 个奇点）。

    即，有一个子图连通且有奇数个奇点，不合图的性质（一个图只可能有偶数个奇点），即不可能出现。

  2. 如果删完所有奇点最后还会剩偶点。

    由于只有偶点的图是欧拉图（或者一些互不连通的欧拉图的并），而且对于每一个子连通图肯定有至少一个点被访问过（如果没有，就违反了原图是连通图的题设）。

    此时我们可以在经过这个偶点的那条路径上插入一条欧拉回路。由于欧拉回路起终点相同，所以并不会破坏路径的性质；而且欧拉图一定会有一个欧拉回路（证明见 OI-WIKI）。

所以可以做到删完奇点后啥也不剩。

所以我们只要对每个连通子图统计奇点个数再除 2 就行了。

注意细节：

代码：

#include<bits/stdc++.h>
#define maxn 200005
using namespace std;
bool vis[maxn];
int n,m,u,w,v,f[maxn],ans = 0,cnt;
vector<int>e[maxn],tmp[maxn];
void dfs(int u,int&id){
    vis[u]=1,tmp[id].push_back(u);
    for(auto v:e[u])if(!vis[v])dfs(v,id);
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= m;i++)
    {
        scanf("%d%d", &u, &v);
        f[v]++;
        f[u]++;
        e[u].push_back(v),e[v].push_back(u);
    } 
    for(int i=1;i<=n;++i)if(!vis[i])dfs(i,++cnt);
    for(int i=1;i<=cnt;++i){
        int tmpans=0,can=0;
        for(auto x:tmp[i]){if(f[x]&1)++tmpans;if(f[x])can=1;}
        tmpans/=2;
        if(!tmpans&&can)++tmpans;
        ans+=tmpans;
    }
    printf("%d", ans);
    return 0;
}