【题解】[CCO2020] Travelling Salesperson

7KByte · 2021-06-07 20:47:06 · 题解

同步发表于我的博客 。

给定一个边权为 0/1 的完全图，对于每个起点 i 构造一条最短的，经过所有点，且边权最多只变化一次的最短路径。

首先要覆盖所有点，所以路径长度不可能优于 n-1 条边。

所以我们考虑构造长度为 n-1 条边的方案。

考虑归纳法，如果前 k-1 个点构造出了 v_1\to v_2 \to \cdots\to v_{k-1} 的路径，考虑加入第 k 个点。

如果路径中所有边的颜色都相同，那么在结尾加入第 k 个点一定合法。

否则原路径存在一个断点 d ，使得 v_d 前面的边是一种颜色，后面的边是另一种颜色。

那么如果 e_{v_d,k} 和 e_{v_{d},v_{d-1}} 颜色相同，那么在 v_d 后面插入 k 一定合法。

否则我们在 v_d 前面插入 k 一定合法。

所以我们只用在线支持插入，直接双向链表即可，时间复杂度 \mathcal{O}(n^2) 。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 2005
using namespace std;
int n,d[N][N],nxt[N],pre[N];char s[N];
inline void ins(int x,int y){nxt[y]=nxt[x];pre[y]=x;pre[nxt[x]]=y;nxt[x]=y;}
inline int g(int x){if(x==n)return 1;return x+1;}
int main(){
    scanf("%d",&n);
    rep(i,2,n){
        scanf("%s",s+1);
        rep(j,1,i-1)d[i][j]=d[j][i]=s[j]=='R';
    }
    rep(i,1,n){
        rep(i,1,n)nxt[i]=pre[i]=0;
        nxt[i]=pre[i]=g(i);pre[g(i)]=nxt[g(i)]=i;
        int op=0,p=i;
        for(int j=g(g(i));j!=i;j=g(j))if(j!=i){
            if(!op){
                if(d[pre[i]][j]!=d[i][nxt[i]])p=pre[i],op=1;
                ins(pre[i],j);
            }
            else{
                if(d[j][p]==d[p][pre[p]]){
                    if(d[j][nxt[p]]==d[j][p])ins(p,j),p=nxt[j];
                    else ins(p,j),p=j;
                }
                else{
                    if(d[j][p]==d[j][pre[p]])ins(pre[p],j),p=pre[j];
                    else ins(pre[p],j),p=j;
                }
                if(p==i||p==pre[i])op=0;
            }
        }
        printf("%d\n%d ",n,i);int cur=nxt[i];
        while(cur!=i)printf("%d ",cur),cur=nxt[cur];
        putchar('\n');
    }
    return 0;
}