题解：CF42D Strange town
caichengyia
·
·
题解
思路
```
0 1 2
1 0 3
2 3 0
```
满足要求。
我们不妨尝试每一次在原图新增一个结点，并求出满足条件的图。
$n=4$ 或 $n=5$ 时，可以设新增的几条边，解方程组。
$n=4$ 时，解得 $\begin{cases}y=x+1\\z=x+2\end{cases}$，邻接矩阵则为
```
0 1 2 4
1 0 3 5
2 3 0 6
4 5 6 0
```
$n=5$ 时，解得 $\begin{cases}y=x+1\\z=x+2\\w=x+4\end{cases}$，邻接矩阵则为
```
0 1 2 4 7
1 0 3 5 8
2 3 0 6 9
4 5 6 0 11
7 8 9 11 0
```
通过观察点连出的旧边权之和与新增边的关系，发现结点 $k$ 与新节点连的边权和节点 $k$ 的旧边权之和之间存在着线性关系。
通过进一步的推算发现，设当前新增第 $n$ 个节点，记 $sum_k$ 为节点 $k$ 的旧边权之和，$d_{k,l}$ 为节点 $k$ 与结点 $l$ 之间的边权，则 $sum_k-sum_1=(n-3)(d_{k,n}-d_{1,n})$。
至于 $d_{1,n}$ 的取值，直接设为 $d_{n-2,n-1}+1$ 就能避免重复。
# 优化
然而，这种做法在 $n=20$ 时边权最大能达到一万多，远超题目限制。
观察到，$n$ 很大时边权跨度非常大，特别浪费。
因为数据范围很小，我们可以不直接将 $d_{1,n}$ 设为 $d_{n-2,n-1}+1$，而是暴力遍历 $1\sim1000$，找出 $d_{1,n}$ 合法的最小取值。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,w[25],d[25][25],fl,f[1005];
signed main(){
cin>>n;
d[1][2]=d[2][1]=1;
d[1][3]=d[3][1]=2;
d[3][2]=d[2][3]=3;
f[1]=f[2]=f[3]=1;
w[1]=3;
w[2]=4;
w[3]=5;
for(int i=4;i<=n;i++){
for(int j=1;j<=1000;j++){
fl=1;
for(int k=1;k<i;k++){
d[i][k]=d[k][i]=(w[k]-w[1])/(i-3)+j;
if(f[d[i][k]]){
fl=0;
break;
}
}
if(fl)break;
}
for(int j=1;j<i;j++){
w[j]+=d[i][j];
w[i]+=d[i][j];
f[d[i][j]]=1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)cout<<d[i][j]<<" ";
cout<<"\n";
}
}
```
时间复杂度为 $O(n^2V)$，空间复杂度为 $O(\max\{n^2,V\})$。