自动搬运

查看原文

来自洛谷，原作者为

	Argon_Cube So now I am trapped in my Eternal Subconscienc∃.

搬运于2025-08-24 21:44:23，当前版本为作者最后更新于2024-02-03 22:19:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

重测了，以前输出样例水过去的都被制裁了。首 A 来一发题解。

显然如果两个人走到一个点上了以后就永远不会再分开，因为保证有解显然任意两个出发点都存在一种走到同一个点上的方案，并且步数显然不会超过 $\binom n2$。

那么我们考虑每次合并两个不在同一点上的人，路径可以通过一次 BFS 得到，最多合并 $n-1$ 次共 $(n-1)\binom n2\leq4\times 10^6$ 次操作。

可以直接让被合并的人在 $1$ 汇合，但是注意到我们需要维护每个点的位置，只能 $\Theta(nk)$ 其中 $k$ 是指令条数。为了让 $k$ 小一些防止超时，我们每次选步数最小的两个人合并，最后所有人会合并在一个点上。再走最多 $n-1$ 步即可让所有人到达 $1$。

#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <bitset>
#include <random>
#include <ctime>
#include <array>
#include <queue>

using namespace std;

array<array<vector<pair<int,int>>,201>,201>	igraph;
array<array<int,201>,201>					graph,dists;
queue<pair<int,int>>						BFSque;
array<int,201>								curnds,dists2;

int main(int argc,char* argv[],char* envp[])
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int cnt,cnte;
	cin>>cnt>>cnte;
	for(int i=1;i<=cnte;i++)
		for(int j=1;j<=cnt;j++)
			cin>>graph[j][i];
	for(int i=1;i<=cnte;i++)
		for(int j=1;j<=cnt;j++)
			for(int k=1;k<=cnt;k++)
				igraph[graph[j][i]][graph[k][i]].emplace_back(j,k);
	for(int i=1;i<=cnt;i++)
		curnds[i]=i,dists[i][i]=1,BFSque.emplace(i,i);
	while(!BFSque.empty())
	{
		int u=BFSque.front().first,v=BFSque.front().second,u0,v0;
		BFSque.pop();
		for(const auto& i:igraph[u][v])
			if(!dists[u0=i.first][v0=i.second])
			{
				dists[u0][v0]=dists[u][v]+1;
				BFSque.emplace(u0,v0);
			}
	}
	BFSque.emplace(1,1);
	dists2[1]=1;
	while(!BFSque.empty())
	{
		int u=BFSque.front().first,u0;
		BFSque.pop();
		for(const auto& i:igraph[u][u])
			if(u0=i.first,!dists2[u0]&&i.first==i.second)
			{
				dists2[u0]=dists2[u]+1;
				BFSque.emplace(u0,u0);
			}
	}
	dists[0][0]=16777216;
	while(true)
	{
		int u=0,v=0,u0,v0;
		for(int i=1;i<=cnt;i++)
			for(int j=i+1;j<=cnt;j++)
				if(curnds[i]!=curnds[j]&&dists[curnds[u]][curnds[v]]>dists[curnds[i]][curnds[j]])
					u=i,v=j;
		if(!u)
			break;
		while((u0=curnds[u])!=(v0=curnds[v]))
		{
			for(int i=1;i<=cnte;i++)
				if(dists[graph[u0][i]][graph[v0][i]]<dists[u0][v0])
				{
					cout<<i<<'\n';
					for(int j=1;j<=cnt;j++)
						curnds[j]=graph[curnds[j]][i];
					break;
				}	
		}
	}
	int u=curnds[1];
	while(u!=1)
		for(int i=1;i<=cnte;i++)
			if(dists2[graph[u][i]]<dists2[u])
				cout<<i<<'\n',u=graph[u][i];
	return 0;
}