Luogu

LOJ

分析

走的路径应满足起点、终点的度数为奇数、其它点的度数为偶数，这个条件长得很像欧拉回路。

我们首先把 $m$ 条关键边连上，然后再在起点、终点间连一条边。这样子会有一些度数为奇数的点，显然相邻的两个间连一条边是最优的。这样子满足了度数限制。

但是我们还需要让图连通。我们把所有连通块缩成一个点，然后求最小生成树，那么可以花费最小生成树上边权和的两倍的代价让图连通起来。

时间复杂度 $\mathcal{O}(n^2\log n)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2500+10,M=3123750+10;

int n,m,s,deg[N];

int f[N],bl[N];
int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }
void merge(int x,int y) { x=find(x),y=find(y); if (x!=y) f[x]=y; }

struct edge { int u,v,w; };
bool operator <(edge a,edge b) { return a.w<b.w; }
vector<edge> e;

int main() {
    n=read(),m=read(),s=read(); ll sum=0;
    for (int i=1;i<=n;++i) f[i]=i;
    for (int i=1;i<=m;++i) {
        int u=read(),v=read();
        ++deg[u],++deg[v],merge(u,v),sum+=abs(u-v);
    }
    for (int i=1;i<=n;++i) bl[i]=find(i);
    for (int t=1;t<=n;++t) {
        for (int i=1;i<=n;++i) f[i]=i;
        ++deg[s],++deg[t],merge(bl[s],bl[t]);
        ll ans=sum;
        for (int i=1,p=0;i<=n;++i) {
            if (!(deg[i]&1)) continue;
            if (!p) p=i;
            else {
                for (int j=p;j<i;++j) merge(bl[j],bl[i]);
                ans+=i-p,p=0;
            }
        }
        e.clear();
        for (int i=1,p=0;i<=n;++i) {
            if (!deg[i]) continue;
            if (p&&find(bl[p])!=find(bl[i]))
                e.emplace_back((edge){bl[p],bl[i],i-p});
            p=i;
        }
        sort(e.begin(),e.end());
        for (auto i:e) {
            int u=i.u,v=i.v,w=i.w<<1;
            if (find(u)!=find(v)) ans+=w,merge(u,v);
        }
        printf("%lld%c",ans," \n"[t==n]);
        --deg[s],--deg[t];
    }
    return 0;
}