一道构造题
qyzyq
·
·
个人记录
P5419 [CTSC2016] 单调上升序列
题面中的证明告诉我们：对于一个带权无向完全图而言，有 n 个点（n 是偶数），有 \frac{n(n-1)}{2} 条边，那么最长的单调上升的路径为 n-1，考虑将每条边边权从小到大排序，每次交换边的两个点，那么所有的点共会被交换 n(n-1) 次，根据鸽巢原理，每个点至少被交换 n-1 次，因为边从小到大排序，所以最长的单调上升路径至少是 n-1。
考虑在这个思路上进行构造：即让每个点都恰好被交换 n-1 次
我们考虑将从小到大枚举边权 w，考虑边权为 w 的边连接哪两个点，然后每 \frac{n}{2} 条边就恰好包含了 n 个点。
这里给出一种构造方式：
将第 n 个点去掉，然后只剩下奇数个点，考虑枚举中间点 i\in[1,n]，让 i 连向 n，然后向左向右扩展，连 \frac{n}{2}-1 条边。
上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=505;
int n,w,g[N][N];
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
g[i][n]=g[n][i]=++w;
for(int u=i,v=i,j=1;j<n/2;j++)
{
u=(u==1)?n-1:u-1;
v=(v==n-1)?1:v+1;
g[u][v]=g[v][u]=++w;
}
}
for(int i=1;i<n;i++)
{
for(int j=i+1;j<=n;j++)
printf("%d ",g[i][j]);
puts("");
}
return 0;
}
```