CF788B Weird journey 欧拉路径+计数

给定一张 $n$ 个点 $m$ 条无向边的图（无重边）：定义一种行走方案为：$m-2$ 条边走 $2$ 次，其余 $2$ 条边只走一次.

两个行走方案不同，当且仅当走一次的两条边中有不同的.

一条边走两次不好处理，可以将每条无向边拆开，然后将问题转换成：有多少种方案使得图中两条边不走的一笔画?

我们知道，对于无向图一笔画的条件是度数为奇数的点不能超过两个，而我们将所有无向边都拆成两个无向边时所有点度数肯定都是偶数的.

因为所有点度数都是偶数，所以如果拆掉一条边，一定会使这条边相连两点度数都变成奇数.

假如说我们拆掉的边不是自环，那么对于另一条需要被删掉的边，可以是自环也可以是这条边所连两个扩展出的所有边（需抛出掉枚举到的这个，就是 -2）

假如说枚举到的是自环，那么是不改变度数的奇偶性的，剩下的那条边随便选一条就行了，有 $(m-1)$ 种选法.

#include <bits/stdc++.h>

#define N 1000005

#define ll long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int p[N],deg[N],from[N],to[N],vis[N],n,m;

int find(int x)

{

    return p[x]==x?x:p[x]=find(p[x]);

}

int main()

{

    ll ans=0;

    int i,j,sum=0,tp=0;

    // setIO("input");

    scanf("%d%d",&n,&m);

    for(i=1;i<=n;++i) p[i]=i;

    for(i=1;i<=m;++i)

    {

        int u,v;

        scanf("%d%d",&u,&v);

        from[i]=u, to[i]=v;

        vis[u]=vis[v]=1;

        if(u==v)

        {

            ++sum;

        }

        else

        {

            ++deg[u], ++deg[v];

            u=find(u), v=find(v);

            if(u!=v) p[u]=v, tp=v;

        }

    }

    for(i=1;i<=n;++i)

        if(vis[i]&&find(i)!=tp)

        {

            printf("0\n");

            return 0;

        }

    for(i=1;i<=m;++i)

    {

        if(from[i]==to[i]) ans+=1ll*(m-1);

        else

        {

            ans+=(ll)deg[from[i]]+deg[to[i]]-2+sum;

        }

    }

    printf("%lld\n",ans/2);

    return 0;

}

巴特西

CF788B Weird journey 欧拉路径+计数

最新文章

热门文章