自动搬运

查看原文

来自洛谷，原作者为

	7KByte **

搬运于2025-08-24 22:22:42，当前版本为作者最后更新于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;
}