【CTSC2016】单调上升路径

  • 本文为博主原创，未经许可不得转载

根据题中所给结论，我们可以证明完全图的最长单调上升路径的长度为$n-1$

所以我们可以构造一种连边的顺序，使得每一轮连的边相互独立

也就是说从同一个点出发的边不在同一轮中被连接起来

这就符合拉丁方阵的性质，即每一行、每一列不出现相同元素

所以我们构造方阵$A$，满足$A$是一个拉丁方阵，且$A_{ij}=A_{ji}$，且$A_{ii}=0$

方阵$A$中的元素$A{ij}$表示<$i,j$>这条边在第$A{ij}$轮被连接起来

那么我们如何来构造这个方阵呢？

有一个很简单的方法：先构造如下的方阵：

第一列 第二列 第三列 第四列 第五列 第六列
0 1 2 3 4 5
1 2 3 4 5 0
2 3 4 5 1 0
3 4 5 1 2 0
4 5 1 2 3 0
5 1 2 3 4 0

我们发现除了第一行比较特殊外，其他行都是第一行的循环位移

构造完成之后，只需要交换$A_{ii}$和$A_{in}$就可以了$(2<=i<=n)$

最后我们只需要根据连边得顺序确定边权即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
int n,c[505],a[505][505];
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)a[1][i]=i-1;
	for(int i=2;i<=n;++i){
		int cnt=i-1;
		for(int j=1;j<n;++j){
			a[i][j]=cnt;
			cnt++;
			if(cnt==n)cnt=1;
		}
	}
	for(int i=2;i<=n;++i)swap(a[i][i],a[i][n]);
	for(int i=2;i<=n;++i)c[i]=c[i-1]+(n>>1);
	for(int i=1;i<=n;++i){
		for(int j=i+1;j<=n;++j)
			printf("%d ",++c[a[i][j]]);
		printf("\n");
	}
	return 0;
}

本文标题:【CTSC2016】单调上升路径

文章作者:chty

发布时间:2017年04月26日 - 09时25分

最后更新:2018年06月08日 - 18时45分

许可协议:本文为博主原创，未经许可不得转载。

文章目录
,