7.18 T1 星际旅行

小鱼儿 2021-11-27 01:02 264阅读 0赞

题意：n个点，m条边，无重边，有自环，要求经过m-2条边两次，2条边一次，问共有多少种本质不同的方案。本质不同：当且仅当至少存在一条边经过次数不同。

题解：考试的时候理解错题，以为他是一棵树，然后我就凉凉了。。。考试感觉今天T1怎么这么难，看了题解才发现这是一道水题。

只有两条边经过一次，其余都经过两次，考虑拆边，把每条边拆成两条，拆完之后每个点的度一定都是偶数，问题就变成了选择两条边删去，使剩下的图形成欧拉路。

删去的边可以有三种情况：

1>任意两条有公共顶点的边

2>任意两个自环

3>一个自环+一条边

然后就是这道题可能不联通（坑了不少人），注意是边不联通而不是点不连通。因为一个点在外边单着没边并不影响题目要求经过边怎么怎么样，但要是外面有个点单着，而且还连着一个自环，那这张图中的所有边不可能组成欧拉路。具体做法是那一个并查集维护这张图的联通性，不联通就直接输出0就行了。

考试的时候由于题意的理解问题，这道题先是按树做的，后来反应过来是张图，脑子怎么抽筋了，开始改，但由于没看出来是欧拉图，改的一塌糊涂，前前后后做这道题大概要有2个小时。（大家都说很显然的欧拉图，但我觉得不是那么显然。。。太菜了）。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #define ll long long
    using namespace std;
    ll n,m,d[100100],fa[100100],in[100100],sum,rt,tot,ans;
    ll find(ll x)
    {
        if(fa[x]!=x) fa[x]=find(fa[x]);
        return fa[x];
    }
    int main()
    {
        scanf("%lld%lld",&n,&m);
        ll u,v;
        for(ll i=1;i<=n;i++) fa[i]=i;
        for(ll i=1;i<=m;i++){
            scanf("%lld%lld",&u,&v);
            ll fx=find(u),fy=find(v);
            if(u==v) sum++;
            else{
                fa[fx]=fy;
                in[u]++;in[v]++;
            }
            d[u]++;d[v]++;
        }
        for(ll i=1;i<=n;i++){
            if(d[i]!=0){
                find(i);
                rt=i;
                break;
            }
        }
        for(ll i=1;i<=n;i++){
            if(d[i]!=0&&find(i)!=fa[rt]){
                puts("0");
                return 0;
            }
        }
        for(ll i=1;i<=n;i++){
            ans+=(in[i]-1)*in[i]/2;
        }
        tot/=2;
        ans+=(sum-1)*sum/2;
        ans+=sum*(m-sum);
        printf("%lld\n",ans);
        return 0;
    }

别颓

转载于:https://www.cnblogs.com/jrf123/p/11209502.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211126/ccc8e4aaff9f40b9ba98fb5d681e860b.png