【欧拉回路+最小生成树】SD开车@山东2018省队一轮集训day1

目录

• 【欧拉回路+最小生成树】SD开车@山东2018省队一轮集训day1
  • PROBLEM
    • 题目描述
    • 输入
    • 输出
    • 样例输入
    • 样例输出
    • 提示
  • SOLUTION
  • CODE

【欧拉回路+最小生成树】SD开车@山东2018省队一轮集训day1

PROBLEM

题目描述

作为钦钦草原最绿的男人，杨某针每天都要开车巡视钦钦草原一圈。

钦钦草原由 n 个城市组成，m 条双向道路连接着它们。经过第 i 条道路要花费的时间是\(2^i\)。

杨某针想要经过每条道路至少一次，在此基础上他想最小化他花费的时间。但作为 曾经 CTSC 的 Cu 选手，他并不能很快地计算出这个问题。所以他向你求助。

输入

输入第一行包含两个正整数n,m。

接下来m行，每行两个正整数\(a_i\),\(b_i\)，表示第i条边连接点\(a_i\)和\(b_i\)，它的权值为\(2^i\)。保证\(a_i\neq b_i\)，不存在重边，且任意两个点之间可以互相到达。

输出

输出一行一个整数，表示答案对\(10^9\)+7取模的值。

样例输入

4 5

1 2

3 4

2 3

1 3

2 4

样例输出

70

提示

最优的路线应当为 1-2-3-4-2-3-1。

对于20%的数据，n,m≤20。

对于40%的数据，n,m≤2,000。

对于100%的数据，n≤400,000,m≤500,000。

SOLUTION

若存在一条从节点S出发的路径，恰好不重不漏地经过每条边一次（可以重复经过图中的节点），最终回到起点S，则称该路径为欧拉回路。存在欧拉回路的无向图被称为欧拉图。

要经过每条道路至少一次，可以对比在欧拉回路中，每条边恰好经过一次。若最佳路线经过某一条边n+1次，可以看作在原图中加上了n次那条边。由原图G加上重复走的边得到G'，G'一定是一个欧拉图，由欧拉图的性质，G'中每个点的度一定为偶数。

题目要求最小花费，也就是要加的边的权值和最小。若我分若干次去添加边，这里可以贪心假设，每次加的一个边集一定是某两个度为奇数的点的最短路径上的边，然后使得这两个点的度变为偶数。

而至于如何去求两个奇数度点的最短路，可以从边的权值上下手——第i条边的权值是\(2^i\)。用求最小生成树的Kruskal算法，我们从按编号（也就是权值）小到大枚举边，然后并查集维护，建出一棵最小生成树。因为\(2^n = 2^{n-1} + 2^{n-2} + ... + 2^1+ 2\) ,所以生成树上两点距离就是原图中两点最短距离（这里需要仔细思考）。

最后dfs遍历生成树，回溯时判断当前点的度数是否为奇数，如果是奇数，让答案再加上该点和它的父节点所连的边的权值，并更新两点的度数。

最终答案要加上原图中所有边的权值和。

CODE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 4e5 + 5;
const int MAXE = 5e5+5;
const int INF = 0x3f3f3f3f;
const ll MOD = 1e9+7;

int degree[MAXN];
int u[MAXE],v[MAXE];

struct edge{
    int u,v,w,nex;
}ed[MAXN<<1];

int head[MAXN],tot;

void addedge(int uu,int vv,int w){
    tot++;
    ed[tot].u = uu;
    ed[tot].v = vv;
    ed[tot].w = w;
    ed[tot].nex = head[uu];
    head[uu] = tot;
}

int fa[MAXN];

int DjsGet(int x){
    if(x==fa[x])return x;
    return fa[x] = DjsGet(fa[x]);
}

ll fastpow(ll a,ll n){
    ll res = 1;
    while(n){
        if(n&1)res=res*a%MOD;
        a = a*a%MOD;
        n>>=1;
    }
    return res;
}

ll ans;

void dfs(int u,int p){
    for(int i=head[u];i;i = ed[i].nex){
        int v = ed[i].v;
        if(i!=(p^1))
            dfs(v,i);
    }
    if(degree[u]&1){
        ans=(ans+fastpow(2,ed[p].w))%MOD;
        degree[u]++;
        degree[ed[p].u]++;
    }
}

int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u[i],&v[i]);
        degree[u[i]]++;
        degree[v[i]]++;
    }
    tot++;
    for(int i = 1;i<=n;i++)fa[i] = i;
    for(int i=1;i<=m;i++){
        int fx = DjsGet(u[i]),fy = DjsGet(v[i]);
        if(fx!=fy){
            fa[fx] = fy;
            addedge(u[i],v[i],i);
            addedge(v[i],u[i],i);
        }
        ans=(ans+fastpow(2,i))%MOD;
    }
    dfs(ed[2].u,0);
    printf("%lld\n",ans);
    return 0;
}