题解：P1636 Einstein学画画

· · 题解

P1636 Einstein学画画

题意

题意

前置知识：详细见 oiwiki

欧拉路径是经过图中每条边恰好一次的路径。

给定一个图 G，将其分成 ans 条欧拉路径，使得所求的 ans 最小。范围满足 1\le n\le 10^3，1\le m\le 10^5。

思考

先看范围 1\le n\le 10^3，1\le m\le 10^5，先一眼盯帧丁真，很容易看出来是欧拉路径，欧拉图一类的东西（可以参考前置知识）。

先发散思考，枚举起始点，再……（以下省略）。有些难写。

那么考虑欧拉路径的特点，一个无向图存在欧拉路径，一定有 0 个奇数点或者 2 个点。依照题意，此时再有更多的奇数点，对于一条欧拉路径已经没有贡献了（应该可以这么说），只能再画一笔，此时按照第一个情况考虑即可，于是就有了 solution。

solution

由于题目没有说明给出的所有点连通，所以枚举每个连通块，对于每个连通块累加奇数度的点，有 cnt 个，如果 cnt 为 0 那么 ans 加 1，否则 ans 加上 \frac{cnt}{2}。

时间复杂度容易计算 O(n)，可以通过本题。

证明

对于每一个连通图，最少的笔画数与奇数度顶点的数量有关。

  1. 当奇数度顶点数量为 0 时，可一笔画成（即存在欧拉回路）；
  2. 当奇数度顶点数量为 2 时，也可一笔画成（存在欧拉路径）；
  3. 当奇数度顶点数量大于 2 时，每两个奇数度顶点可以作为一条路径的起点和终点，因此最少笔画数为奇数度顶点数量除以 2。

小证明（作者做题脑抽时考虑到的）

作者疑问：对于一张无向图，有可能只有一个奇数度的点。

作者回答：在任何无向图中，所有顶点的度数之和等于边数的两倍。因为每条边都会贡献两个端点，所以总度数必然是偶数。

Code

还是有一些小细节要注意。作者是蒟蒻，欢迎大家的 hack。

#include<bits/stdc++.h>
#define ll long long
#define lll unsigned long long
#define dou double
#define S string
#define INF 2147483647
#define pi pair<ll,ll>
#define mkp make_pair
#define gc getchar
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;

const int N=1011;

int n,m,ans,sum,cnt;
int d[N];
bool vis[N];
vector<int> a[N];

void dfs(int step)              //dfs求连通块
{
    if(d[step]&1) cnt++;        //x&1==1，表示x是奇数
    vis[step]=1;
    for(auto i:a[step])
    {
        if(vis[i]) continue;
        dfs(i);
    }
}

int main()
{
    IOS;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        d[x]++;
        d[y]++;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            cnt=0;
            dfs(i);                     //由于vis记录过了，所以复杂度实际上是O(n)。
            if(a[i].empty()) continue;  //若这个连通块只有一个点，没有边，答案不会变化
            if(cnt) ans+=cnt/2;         //详见solution
            else ans++;
        }
    }
    cout<<ans<<endl;
    return 0;
}
/*

*/