专栏文章

题解：P3561 [POI 2017] Turysta

FFelix72
P3561题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3nns5
此快照首次捕获于
2025/12/01 20:02
3 个月前
此快照最后确认于
2025/12/01 20:02
3 个月前
查看原文
首先用兰道定理找出该图的所有 scc\text{scc}。（兰道定理有推论如下：将这个图的出度序列从小到大排序，若当前 ii 个点的加和是下界 (i2)i \choose 2，则前 ii 个点没有连向后 n−in - i 个点的任何一条边。）
容易知道一个点的答案上界是他所在 scc\text{scc} 和拓扑序在其之后的所有 scc\text{scc} 的大小加和。下面将用构造证明这一上界总被达到。
我们将尝试对于每个强连通竞赛图找出其哈密顿回路（找出所有 scc\text{scc} 的哈密顿回路之后原问题是简单的）。
第一步，对于任意竞赛图构造哈密顿路径。考虑增量法构造，我们动态维护一条路径，每次加入一个点是判断其是否能插入在链头、链尾或者中间的某个位置（容易证明至少可以插入在其中一个位置）
第二步，对于任意强连通竞赛图构造哈密顿回路。先提取出哈密顿路径，再按照路径的顺序加入节点。我们手头维护的是一个环和一条路径（路径是原哈密顿路径的一部分）。每次先把当前节点放到路径的最后，再枚举环的所有位置，如果能把整条路经插入环的某个位置就直接插。可以证明最后不会剩下路径的某一部分，否则原图不是强连通的。
最后按照题设顺序输出若干个 scc\text{scc} 的哈密顿回路即可。
CPP
/* K_crane x N_cat */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 2010;
int n, s[N], rnk[N]; bool mp[N][N];
inline bool cmp(int x, int y) {return s[x] < s[y];}
vector < int > con[N], path[N], loop[N], ans[N]; int m;

int main()
{
//	freopen("text.in", "r", stdin);
//	freopen("prog.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j < i; ++j)
		{
			int x; cin >> x;
			if(x == 1) mp[j][i] = true, ++s[j];
			else mp[i][j] = true, ++s[i];
		}
	}
	
	/*
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= n; ++j)
			cerr << mp[i][j];
		cerr << '\n';
	}
	*/
	
	for(int i = 1; i <= n; ++i) rnk[i] = i;
	sort(rnk + 1, rnk + n + 1, cmp);
	for(int i = 1, sum = 0, lst = 0; i <= n; ++i)
	{
		sum += s[rnk[i]];
		if(sum == i * (i - 1) / 2)
		{
			++m;
			for(int j = lst + 1; j <= i; ++j) con[m].push_back(rnk[j]);
			lst = i;
		}
	}
	for(int i = 1; i <= m / 2; ++i) swap(con[i], con[m - i + 1]);
	for(int ID = 1; ID <= m; ++ID)
	{
		path[ID].push_back(con[ID][0]);
		for(int i = 1; i < (int)con[ID].size(); ++i)
		{
			int pt = con[ID][i];
			if(mp[pt][path[ID][0]])
			{
				path[ID].push_back(0);
				for(int j = (int)path[ID].size() - 1; j >= 1; --j)
					path[ID][j] = path[ID][j - 1];
				path[ID][0] = pt;
			}
			else if(mp[path[ID].back()][pt]) path[ID].push_back(pt);
			else
			{
				for(int j = 0; j < (int)path[ID].size() - 1; ++j)
				{
					if(mp[path[ID][j]][pt] && mp[pt][path[ID][j + 1]])
					{
						path[ID].push_back(0);
						for(int k = (int)path[ID].size() - 1; k > j + 1; --k)
							path[ID][k] = path[ID][k - 1];
						path[ID][j + 1] = pt;
						break;
					}
				}
			}
		}
		/*
		cerr << "-> ";
		for(int x : path[ID]) cerr << x << " ";
		cerr << '\n';
		*/
		loop[ID].push_back(path[ID][0]); deque < int > dq;
		for(int i = 1; i < (int)path[ID].size(); ++i)
		{
			int pt = path[ID][i]; dq.push_back(pt);
			if(mp[loop[ID].back()][dq.front()] && mp[dq.back()][loop[ID].front()])
			{
				for(int x : dq) loop[ID].push_back(x);
				dq.clear();
			}
			else
			{
				for(int j = 0; j < (int)loop[ID].size() - 1; ++j)
				{
					if(mp[loop[ID][j]][dq.front()] && mp[dq.back()][loop[ID][j + 1]])
					{
						vector < int > tmp;
						for(int k = 0; k <= j; ++k) tmp.push_back(loop[ID][k]);
						for(int x : dq) tmp.push_back(x); dq.clear();
						for(int k = j + 1; k < (int)loop[ID].size(); ++k) tmp.push_back(loop[ID][k]);
						loop[ID] = tmp;
						break;
					}
				}
			}
		}
		/*
		cerr << "loop : ";
		for(int x : loop[ID]) cerr << x << " ";
		cerr << '\n';
		*/
	}
	
	for(int ID = 1; ID <= m; ++ID)
	{
		for(int i = 0; i < (int)loop[ID].size(); ++i)
		{
			int S = loop[ID][i];
			for(int j = i; j < (int)loop[ID].size(); ++j) ans[S].push_back(loop[ID][j]);
			for(int j = 0; j < i; ++j) ans[S].push_back(loop[ID][j]);
			for(int j = ID + 1; j <= m; ++j)
				for(int x : loop[j])
					ans[S].push_back(x);
		}
	}
	
	for(int i = 1; i <= n; ++i)
	{
		cout << ans[i].size() << " ";
		for(int x : ans[i]) cout << x << " ";
		cout << '\n';
	}
	return 0;
}
/*

*/

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...