zkx06111's Blog

Chinese Postman Problem

| Comments

XJOI上竟然有人出这道题,不怕被寄刀片嘛...

有一个无向图( ),一个邮递员从一个点出发,经过所有边(可以重复经过)回到起点,求边权和最小的方案。

首先,非联通图不存在方案;其次,一个全是偶点的图,只需要求出它的欧拉回路。

处理完这些情况之后,这个图中一定存在偶数个奇点。因为每条边都会对总的度数产生2的贡献,所以总度数是偶数,所以不可能存在奇数个奇点。也就是说,只需要把这些奇点两两匹配,加上边变成偶点(匹配的两个点的边权赋值为它们在原图中的最短路径,相当于重复经过这段路径)。一般图的最大权匹配存在复杂度为的带花树算法。于是这题就做完了。(然而我不会带花树,于是去UOJ上拖了一份代码)。

#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <ctime>
#include <vector>
#include <queue>
#include <climits>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define PER(i, a, b) for (int i = a; i >= b; --i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
 
inline int read(){
    int x = 0, ch = getchar(), f = 1;
    while (!isdigit(ch)){if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}
 
typedef unsigned short ush;
const int INF = 0x3f3f3f3f, infin = 100000000;
int n, m, g[205][205], du[205], fa[205], vis[205], odd[205];
int fr[205], tote, route[205], pre[205][205];
int ans = 0, len, cnt;
 
struct Edge{
    short to;
    int w;
    unsigned short nxt, vis;
} G[40005];
 
int Find(int x){
    //printf("%d\n", x);
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}
 
inline void addedge(int x, int y, int z){
    ++du[x]; ++du[y]; ans += z;
    g[x][y] = g[y][x] = z;
    G[tote++] = (Edge){y, z, fr[x]}; fr[x] = tote - 1;
    G[tote++] = (Edge){x, z, fr[y]}; fr[y] = tote - 1;
    x = Find(x); y = Find(y);
    fa[x] = y;
}
 
void dfs(int x){
    for (int i = fr[x]; i != (ush)-1; i = G[i].nxt){
        if (G[i].vis) continue;
        G[i].vis = G[i ^ 1].vis = 1;
        route[++len] = G[i].to;
        dfs(G[i].to);
    }
}
 
void orz(int x, int y){
    if (pre[x][y] == 0){
        addedge(x, y, g[x][y]);
        return;
    }
    orz(x, pre[x][y]);
    orz(pre[x][y], y);
}
 
#define MAXN 150
 
namespace Tree_with_flowers{
 
struct edge{
    int u,v,w;
    edge(){}
    edge(int u,int v,int w):u(u),v(v),w(w){}
};
int n,n_x;
edge g[MAXN*2+1][MAXN*2+1];
int lab[MAXN*2+1];
int match[MAXN*2+1],slack[MAXN*2+1],st[MAXN*2+1],pa[MAXN*2+1];
int flower_from[MAXN*2+1][MAXN+1],S[MAXN*2+1],vis[MAXN*2+1];
vector<int> flower[MAXN*2+1];
queue<int> q;
inline int e_delta(const edge &e){ // does not work inside blossoms
    return lab[e.u]+lab[e.v]-g[e.u][e.v].w*2;
}
inline void update_slack(int u,int x){
    if(!slack[x]||e_delta(g[u][x])<e_delta(g[slack[x]][x]))slack[x]=u;
}
inline void set_slack(int x){
    slack[x]=0;
    for(int u=1;u<=n;++u)
        if(g[u][x].w>0&&st[u]!=x&&S[st[u]]==0)update_slack(u,x);
}
void q_push(int x){
    if(x<=n)q.push(x);
    else for(size_t i=0;i<flower[x].size();i++)q_push(flower[x][i]);
}
inline void set_st(int x,int b){
    st[x]=b;
    if(x>n)for(size_t i=0;i<flower[x].size();++i)
            set_st(flower[x][i],b);
}
inline int get_pr(int b,int xr){
    int pr=find(flower[b].begin(),flower[b].end(),xr)-flower[b].begin();
    if(pr%2==1){//檢查他在前一層圖是奇點還是偶點
        reverse(flower[b].begin()+1,flower[b].end());
        return (int)flower[b].size()-pr;
    }else return pr;
}
inline void set_match(int u,int v){
    match[u]=g[u][v].v;
    if(u>n){
        edge e=g[u][v];
        int xr=flower_from[u][e.u],pr=get_pr(u,xr);
        for(int i=0;i<pr;++i)set_match(flower[u][i],flower[u][i^1]);
        set_match(xr,v);
        rotate(flower[u].begin(),flower[u].begin()+pr,flower[u].end());
    }
}
inline void augment(int u,int v){
    for(;;){
        int xnv=st[match[u]];
        set_match(u,v);
        if(!xnv)return;
        set_match(xnv,st[pa[xnv]]);
        u=st[pa[xnv]],v=xnv;
    }
}
inline int get_lca(int u,int v){
    static int t=0;
    for(++t;u||v;swap(u,v)){
        if(u==0)continue;
        if(vis[u]==t)return u;
        vis[u]=t;//這種方法可以不用清空v陣列
        u=st[match[u]];
        if(u)u=st[pa[u]];
    }
    return 0;
}
inline void add_blossom(int u,int lca,int v){
    int b=n+1;
    while(b<=n_x&&st[b])++b;
    if(b>n_x)++n_x;
    lab[b]=0,S[b]=0;
    match[b]=match[lca];
    flower[b].clear();
    flower[b].push_back(lca);
    for(int x=u,y;x!=lca;x=st[pa[y]])
        flower[b].push_back(x),flower[b].push_back(y=st[match[x]]),q_push(y);
    reverse(flower[b].begin()+1,flower[b].end());
    for(int x=v,y;x!=lca;x=st[pa[y]])
        flower[b].push_back(x),flower[b].push_back(y=st[match[x]]),q_push(y);
    set_st(b,b);
    for(int x=1;x<=n_x;++x)g[b][x].w=g[x][b].w=0;
    for(int x=1;x<=n;++x)flower_from[b][x]=0;
    for(size_t i=0;i<flower[b].size();++i){
        int xs=flower[b][i];
        for(int x=1;x<=n_x;++x)
            if(g[b][x].w==0||e_delta(g[xs][x])<e_delta(g[b][x]))
                g[b][x]=g[xs][x],g[x][b]=g[x][xs];
        for(int x=1;x<=n;++x)
            if(flower_from[xs][x])flower_from[b][x]=xs;
    }
    set_slack(b);
}
inline void expand_blossom(int b){ // S[b] == 1
    for(size_t i=0;i<flower[b].size();++i)
        set_st(flower[b][i],flower[b][i]);
    int xr=flower_from[b][g[b][pa[b]].u],pr=get_pr(b,xr);
    for(int i=0;i<pr;i+=2){
        int xs=flower[b][i],xns=flower[b][i+1];
        pa[xs]=g[xns][xs].u;
        S[xs]=1,S[xns]=0;
        slack[xs]=0,set_slack(xns);
        q_push(xns);
    }
    S[xr]=1,pa[xr]=pa[b];
    for(size_t i=pr+1;i<flower[b].size();++i){
        int xs=flower[b][i];
        S[xs]=-1,set_slack(xs);
    }
    st[b]=0;
}
inline bool on_found_edge(const edge &e){
    int u=st[e.u],v=st[e.v];
    if(S[v]==-1){
        pa[v]=e.u,S[v]=1;
        int nu=st[match[v]];
        slack[v]=slack[nu]=0;
        S[nu]=0,q_push(nu);
    }else if(S[v]==0){
        int lca=get_lca(u,v);
        if(!lca)return augment(u,v),augment(v,u),true;
        else add_blossom(u,lca,v);
    }
    return false;
}
inline bool matching(){
    memset(S+1,-1,sizeof(int)*n_x);
    memset(slack+1,0,sizeof(int)*n_x);
    q=queue<int>();
    for(int x=1;x<=n_x;++x)
        if(st[x]==x&&!match[x])pa[x]=0,S[x]=0,q_push(x);
    if(q.empty())return false;
    for(;;){
        while(q.size()){
            int u=q.front();q.pop();
            if(S[st[u]]==1)continue;
            for(int v=1;v<=n;++v)
                if(g[u][v].w>0&&st[u]!=st[v]){
                    if(e_delta(g[u][v])==0){
                        if(on_found_edge(g[u][v]))return true;
                    }else update_slack(u,st[v]);
                }
        }
        int d=INF;
        for(int b=n+1;b<=n_x;++b)
            if(st[b]==b&&S[b]==1)d=min(d,lab[b]/2);
        for(int x=1;x<=n_x;++x)
            if(st[x]==x&&slack[x]){
                if(S[x]==-1)d=min(d,e_delta(g[slack[x]][x]));
                else if(S[x]==0)d=min(d,e_delta(g[slack[x]][x])/2);
            }
        for(int u=1;u<=n;++u){
            if(S[st[u]]==0){
                if(lab[u]<=d)return 0;
                lab[u]-=d;
            }else if(S[st[u]]==1)lab[u]+=d;
        }
        for(int b=n+1;b<=n_x;++b)
            if(st[b]==b){
                if(S[st[b]]==0)lab[b]+=d*2;
                else if(S[st[b]]==1)lab[b]-=d*2;
            }
        q=queue<int>();
        for(int x=1;x<=n_x;++x)
            if(st[x]==x&&slack[x]&&st[slack[x]]!=x&&e_delta(g[slack[x]][x])==0)
                if(on_found_edge(g[slack[x]][x]))return true;
        for(int b=n+1;b<=n_x;++b)
            if(st[b]==b&&S[b]==1&&lab[b]==0)expand_blossom(b);
    }
    return false;
}
inline pair<long long,int> weight_blossom(){
    memset(match+1,0,sizeof(int)*n);
    n_x=n;
    int n_matches=0;
    long long tot_weight=0;
    for(int u=0;u<=n;++u)st[u]=u,flower[u].clear();
    int w_max=0;
    for(int u=1;u<=n;++u)
        for(int v=1;v<=n;++v){
            flower_from[u][v]=(u==v?u:0);
            w_max=max(w_max,g[u][v].w);
        }
    for(int u=1;u<=n;++u)lab[u]=w_max;
    while(matching())++n_matches;
    for(int u=1;u<=n;++u)
        if(match[u]&&match[u]<u)
            tot_weight+=g[u][match[u]].w;
    return make_pair(tot_weight,n_matches);
}
inline void init_weight_graph(){
    for(int u=1;u<=n;++u)
        for(int v=1;v<=n;++v)
            g[u][v]=edge(u,v,0);
}
 
 
 
};
 
void dhs(){
    Tree_with_flowers::n = cnt;
    Tree_with_flowers::init_weight_graph();
    REP(i, 1, cnt) REP(j, i + 1, cnt){
        int u = odd[i], v = odd[j];
        Tree_with_flowers::g[i][j].w = Tree_with_flowers::g[j][i].w = infin - g[u][v];
    }
    Tree_with_flowers::weight_blossom().first;
    memset(vis, 0, sizeof vis);
     
    int *tm = Tree_with_flowers::match;
    //REP(i, 1, cnt) debug("link %d %d\n", i, tm[i]);
    REP(i, 1, cnt) if (tm[i] && i < tm[i]) orz(odd[tm[i]], odd[i]);
}
 
 
int main(){
    srand(time(0));
    n = read(), m = read();
     
    REP(i, 1, n) REP(j, i + 1, n)
        g[i][j] = g[j][i] = INF;
    memset(fr, -1, sizeof fr);
    REP(i, 1, n) fa[i] = i;
     
    REP(i, 1, m){
        int x = read(), y = read(), z = read();
        addedge(x, y, z);
    }
    cnt = 0;
    REP(i, 1, n){
        if (!vis[Find(i)]) vis[Find(i)] = 1, ++cnt;
    }
    if (cnt > 1) return printf("IMPOSSIBLE\n"), 0;
    cnt = 0;
    REP(i, 1, n) if (du[i] & 1) odd[++cnt] = i;
    if (cnt == 0){
        printf("%d\n", ans);
        dfs(1);
        printf("%d", 1);
        REP(i, 1, len) printf(" %d", route[i]);
        printf("\n"); return 0;
    }
     
    REP(k, 1, n) REP(i, 1, n) REP(j, 1, n)
        if (g[i][j] > g[i][k] + g[k][j]){
            g[i][j] = g[i][k] + g[k][j];
            pre[i][j] = k;
        }
    dhs(); 
     
    printf("%d\n", ans);
    dfs(1);
    printf("%d", 1);
    REP(i, 1, len) printf(" %d", route[i]);
    printf("\n");
    return 0;
}

Comments

comments powered by Disqus