有一张nn（nn为偶数）个点的完全图GG，你需要为每条边确定一个不同的边权，使得这张图的最长单调上升路径边数最少

n≤500n\le 500

原题中还给出了一个提示：

结论：假设带权无向图 GG 有 100100 个节点 10001000 条边，且所有权值各不相同。那么，GG 中一定存在一个单调上升路径，它的长度大于等于 2020。

证明：假设每个节点上有一个探险家。我们按权值从小到大枚举所有的边，每次将该边连接的节点中的探险家的位置进行对调。可以知道，每个探险家都走的是一条单调上升路径。另外，由于共有 100100 个探险家，而探险家一共走了 20002000 步，所以有人走了 2020 步。证毕。

UOJ 201

Solution

由提示可以知道，一张nn个点mm条边的图，单调上升路径至少为2mn\frac{2m}{n}

因此完全图的单调上升路径至少为n−1n-1，且所有极长单调上升路径长度都为

接下来，考虑把完全图的边分解成n−1n-1个大小为n2\frac{n}{2}的集合，每个集合的边都不在端点处相交

对于第ii个集合，我们对其赋予从n2×(i−1)+1\frac{n}{2}\times (i - 1) + 1到n2×i\frac{n}{2}\times i大小的边权

这样最长上升路径显然不超过n−1n-1，因为每组边集里的边都最多只经过一次

具体构造这个东西的话，可以把n−1n-1个点围成一个圈，中间放一个点

19-2-24-1

每次构造这样的n2\frac{n}{2}条边，然后把这个多边形旋转一下

特别神仙的一个构造。。。

Code

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 500 + 10;

int N;
int A[Maxn][Maxn];

inline int Pos (int x) { return (x + N - 2) % (N - 1) + 1; }

inline void add_edge (int x, int y, int z)
{
	if (x > y) swap(x, y);
	A[x][y] = z;
}

inline void Solve ()
{
	int cnt = 0, K = N / 2 - 1;
	for (int i = 1; i < N; ++i)
	{
		add_edge (i, N, ++cnt);
		for (int j = 1; j <= K; ++j)
			add_edge (Pos(i + j), Pos(i - j), ++cnt);
	}

	for (int i = 1; i < N; ++i)
		for (int j = i + 1; j <= N; ++j)
			printf("%d%c", A[i][j], j == N ? '\n' : ' ');
}

inline void Input ()
{
	N = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}