目前题解区还没有证明，我交个证明。
形式化题意
给定每个点的度数 \(d_i\)，请构造一个简单无向图（无重边无自环）。
First. 无解
首先，根据握手定理，每个无向图的度数之和为边数的两倍，所以如果度数之和为奇数，那么肯定无解。
但是发现，这种情况之外还有别的无解情况（本题有 \(3\) 个无解数据，只能 AC 一个）。
而这种情况，就需要给出一个保证正确的构造方案，如果无法构造那么无解。
Second. 构造
这里介绍一个定理：
Havel-Hakimi定理
一个不降序度数序列 \(d = \{d_1,d_2,\dots, d_n\}\) 若其可以简单图化，当且仅当 \(d' = \{ d_2 - 1, d_3 - 1, \dots,d_{d_1 + 1} - 1,d_{d_1+2},\dots,d_n \}\) 可以简单图化。
-
证明：\(d\) 若其可以简单图化，那么 \(d'\) 可以简单图化。
两种情况：
- 图 \(G\) 中存在边 \(\{ (1, 2),(1,3),\dots,(1,d_1 + 1)\}\)，显然，此时删去这些边该图仍然为简单图且满足度数序列 \(d'\)，所以 \(d'\) 可简单图化。
- 图 \(G\) 中存在点对 \((i, j)\) 满足 \(d_i \ge d_j\) 且仅存在边 \((1,j)\) 而不存在边 \((1,i)\) 且 \(i \le d_1 + 1,j > d_1 + 1\)，那么此时由于 \(d_i \ge d_j\) 那么一定存在一个点 \(u\) 满足存在 \((i, u)\) 但不存在 \((j, u)\)，将 \((i, u)\) 修改为 \((1, u)\)，\((1, j)\) 修改为 \((j, u)\)，该图度数序列不变且仍然为简单图，此时，情况又变为情况 \(1\)。
-
证明：\(d'\) 可以简单图化，那么 \(d\) 可以简单图化。
构造很简单，\(1\) 与 \(2, 3,\dots, d_1 + 1\) 连边，该图仍为简单图，且度数序列变为 \(d\)。
显然，度数序列 \(d = \{0, 0, \dots, 0\}\) 一定可以简单图化，那么只需要重复运用定理，直至度数序列化为 \(d = \{ 0,0 , \dots, 0\}\) 即可。
如果不能进行如上操作（即 \(d_i - 1 < 0 (2 \le i \le d_1 + 1)\)），那么无解。
注意，定理中的 \(d\) 是不降序度数序列，那么每次操作后需要排序才能再次进行操作。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int n;
pair<int, int> g[N];
vector<int> ans[N];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
int d = 0;
for (int i = 1; i <= n; i ++) {
cin >> g[i].first;
g[i].second = i, d += g[i].first;
}
if (d & 1) { // 握手定理
cout << "NO SOLUTION\n";
return 0;
}
for (int t = 1; t <= n; t ++) {
sort(g + 1, g + 1 + n); // 排序
int j = n - 1;
while (g[n].first) { // 从次大值开始减
g[j].first --, g[n].first --;
if(g[j].first < 0) { //无法加边，无解
cout << "NO SOLUTION\n";
return 0;
}
ans[g[j].second].push_back(g[n].second);
ans[g[n].second].push_back(g[j].second);
j --;
}
}
cout << "SOLUTION\n";
for (int i = 1; i <= n; i ++) {
for (auto u : ans[i]) cout << u << ' ';
cout << endl;
}
return 0;
}