题解——星际旅行（欧拉路）

一道很巧妙的欧拉路问题，细节也要注意

题面

Description
题面已隐藏

Input
一个图

Output
一个整数表示最低花费

in.1
5 4
1 2
1 3
1 4
1 5

out.1
6

数据范围与约定

对于100%数据，n,m<=1e5 ,其他隐藏

思路

主要思路
由题意得，我们只需要将每条边翻倍，再在所有边中选择两条不同的边，将其删除，如果满足欧拉路或者欧拉回路，就可以得到一种本质不同的方案。

主要分为两部分：

1.判断联通，如果不连通，方案数肯定为0
2.分类统计处理贡献

处理：

1.判断联通可以建图跑一次dfs个每条边打标记，也可以不建图用并查集，两种方法都是 O(n)

2.好了关键来了。

前提：边翻倍后，所有点的度数变为偶数。
Cndition1：删除两个自环。由于自环对一个点的影响都是偶数，任意选择两个自环删去，所以始终满足欧拉回路。ans += C( 2 , m )
Cndition2：删除一个自环+一条边。由于自环对一个点的影响都是偶数，忽略，而一条边使两个点的度数变为奇数，所以始终满足欧拉路。ans += 路径条数 X 自环数
Cndition3：删除两条边，无法满足欧拉回路条件，要保证满足欧拉路条件，选择的两条边一定有一个共同点。所以对每个初始度数（不翻倍）>= 2 的点，统计贡献 。 ans += ∑ C( 2 , du[ i ] )。

细节：
1.如使用dfs判联通，注意累计次数退出环，否则爆栈。
2.由于不能删翻倍后的同一条重边，上述做法中删除后图始终保持联通。

DFS版本（from ssw02 )

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int MAXN = 100005 ;
inline int read(){
    int s=0 ;char g=getchar(); while(g>'9'||g<'0')g=getchar() ; 
    while( g>='0'&&g<='9')s=s*10+g-'0',g=getchar() ; return s ;
}
ll ans = 0LL , sum = 0LL , cnt = 0LL , du[ MAXN ] ;
int  N , M , head[ MAXN ] , to[ MAXN*2 ] , nex[ MAXN*2 ] , tot = 1 , vis[ MAXN ];//边 自环 
bool  used[ MAXN*2 ] , key ;
void  add( int x , int y ){
    to[ ++tot ] = y , nex[ tot ] = head[ x ] , head[ x ] = tot ;
}
void  check(){
    for( int i = 2 ; i <= tot ; ++i )
        if( !used[ i ] ){
            key = true ; break ;
        }
}
void  dfs( int u , int fa ){
    vis[ u ]++ ;
    if( vis[ u ] > 10 )return ;//平时开大点，这里数据水
    for( int i = head[ u ] ; i ; i = nex[ i ] ){
        used[ i ] = true ;
        if( to[i] == fa || to[ i ] == u )continue ;
        dfs( to[i] , u ) ;
    }
}
int main(){
    N = read() , M = read() ; int  m1 , m2 ;
    for( int i = 1 ; i <= M ; ++i ){
        m1 = read() , m2 = read() ; add( m1 , m2 ) , add( m2 , m1 ) ;
        if( m1 != m2 )
            sum++ , du[ m1 ]++ , du[ m2 ]++ ;
        else cnt++ ;
    }
    for( int i = 1 ; i <= N ; ++i )
        if( head[ i ] ){dfs( i , i )  ; break ;}
    check();
    if( key ){ printf("0");return 0 ;}
    if( cnt >= 2 )
        ans = (ll)cnt*(ll)(cnt-1LL)/2LL ;
    if( cnt >= 1 && sum >= 1 )
        ans += (ll)sum*cnt ;
    if( sum >= 2 )
        for( int i = 1 ; i <= N ; ++i )
            ans += ( (ll)du[i]*(du[i]-1LL) )/2LL ;
    cout<<ans ;
} 

并查集版本（std）

#include<cstdio>
#include<iostream>
using namespace std;
#define maxn 1000010
int fa[maxn],siz[maxn];
int findfa(int p)
{
    if(fa[p]!=p) fa[p]=findfa(fa[p]);
    return fa[p];
}
void uni(int p,int q)
{
    p=findfa(p),q=findfa(q);
    if(p!=q)
    {
        fa[p]=q;
        siz[q]+=siz[p];
    }
}
int n,m,l[maxn],r[maxn];
int du[maxn],sig;
bool v[maxn];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) fa[i]=i,siz[i]=1;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&l[i],&r[i]);
        uni(l[i],r[i]);
        if(l[i]!=r[i])
        {
            du[l[i]]++;
            du[r[i]]++;
        }
        else sig++;
    }
    int lst=findfa(l[1]);
    for(int i=2; i<=m; i++)
        if(findfa(l[i])!=lst) {lst=-1; break;}
    if(lst==-1) cout<<0<<endl;
    else
    {
        long long ans=0;
        ans+=1ll*sig*(sig-1)/2;
        ans+=1ll*sig*(m-sig);
        for(int i=1; i<=n; i++)
            ans+=1ll*du[i]*(du[i]-1)/2;
        cout<<ans<<endl;
    }
    return 0;
}

如有不足，请大佬指出

题解——星际旅行（欧拉路）

原文：https://www.cnblogs.com/ssw02/p/11409002.html