Solution of CF21D Traveling Graph

· · 题解

解决本题的一个重要知识：欧拉路径。

在这里简单介绍一下欧拉路径，我们定义一个点连接它的边的数量为它的度，定义度数为奇数的点为奇点，度数为偶数的点为偶点。对于一个无向图 G，奇点个数为 2 时为欧拉路，从任意奇点出发可以遍历所有边，最后走到另一个奇点；奇点的个数为 0 时为欧拉回路,此时从任意一个点出发可以遍历所有的点，最后回到出发点，所有的边都只经过一遍，其余情况都无法一遍走完所有边。

那么对于本题，我们要从 1 出发最后回到 1 ,如果此时的图构成了欧拉回路，那么直接把所有边的权值加起来即可。如果不是欧拉回路，我们需要重复经过一些边才能回到出发点，其实把重复经过的边算到原图上，就相当于把原图变成了欧拉回路。再回到欧拉回路的定义，这就相当于我们要把度数为奇数的点的度数变成偶数。

具体要怎样实现呢？我们很容易发现，每连一条边可以让两个点的度数 +1,那么我们每次选两个奇点，把它们之间最短的路径再走一遍，最后把所有奇点都考虑到。对于选取的方案，我们发现本题的数据范围非常小，可以考虑状态压缩。令当前已经选取的奇点集合为 S,有

dp_{S \cup \{j,k\}}=\min _{j,k\notin S }(dp_S+dis_{jk})

最后的 dp_S 就是回到 1 所需要重复经过的边的总长度。

code 

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,inf=1e9;
int d[40][40];//d表示两点的距离 
int deg[35],f[1<<21];//deg表示点的度数，f为重复经过的边 
int n,m,cnt,ans,tot,a[40];//a为奇点的集合 
void floyed(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i!=j&&i!=k&&j!=k){
                    d[i][j]=min(d[i][k]+d[k][j],d[i][j]);
                }
            }
        }
    }
} 
int cc(int num){
    int res=0;
    while(num){
        num>>=1;
        res++;
    }
    return res;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            d[i][j]=inf;
        }
    }
    for(int i=1,x,y,w;i<=m;i++){
        cin>>x>>y>>w;
        if(x!=y){
            d[x][y]=min(d[x][y],w);//重边只考虑最小的 
            d[y][x]=d[x][y];
        }
        deg[x]++,deg[y]++;
        ans+=w;
    }
    floyed();//n^3处理每两个点的距离
    for(int i=2;i<=n;i++){
        if(deg[i]&&d[1][i]==inf){//非连通图且那个点连的有边 
            cout<<-1;
            return 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(deg[i]&1)a[++tot]=i;
    }
    f[0]=0,cnt=(1<<tot)-1;
    for(int i=1;i<=cnt;i++){
        f[i]=inf;
        if(cc(i)&1)continue;//奇点的个数一定为偶数 
        for(int j=1;j<=tot;j++){
            if((i&1<<(j-1))==0)continue;
            for(int k=j+1;k<=tot;k++){
                if((i&1<<(k-1))==0)continue;
                int s=i^(1<<(j-1))^(1<<(k-1));
                f[i]=min(f[s]+d[a[j]][a[k]],f[i]);
            }
        }
    }
    cout<<ans+f[cnt];//end 
    return 0;
}