UVa1667/LA3405 Network Mess

本文主要是介绍UVa1667/LA3405 Network Mess，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVa1667/LA3405 Network Mess

题目链接
题意
分析
AC 代码

题目链接

本题是2005年icpc亚洲区域赛东京赛区的题目

题意

有一棵n（n≤50）个叶子的无权树。输入两两叶子的距离，恢复出这棵树并输出每个非叶子结点的度数。

分析

先处理1、2号叶结点，其距离为a[1][2]，则有a[1][2]-1个初始非叶结点，且每个非叶结点i到1、2号叶结点的距离d[i][1]、d[i][2]都知道。再考虑加入3号叶节点多出来的那一个分支：先找出是从初始的a[1][2]-1个非叶结点哪一个结点开始延伸出来的，假设是结点x，则a[1][3]-a[2][3] == d[x][1]-d[x][2]，后面需要再添加a[1][3]-d[x][1]-1个非叶结点，并且新添加的每个非叶结点k到1、2、3号叶结点的距离d[k][1]、d[k][2]、d[k][3]都容易得到，但还需要计算出初始的a[1][2]-1个非叶结点到3号叶结点，这个就不直观了，高效的计算方法稍后再说。
一般地，加入第i（i>2）号结点后，首先找出是从已经存在的m个非叶结点的哪个结点开始延伸出来，可以通过最多m*(i-2)次的遍历判断找出（二重循环）：外层循环枚举m个非叶结点x，内层循环枚举k（0<k<i），如果a[k-1][i]-a[k][i] != d[x][k-1]-d[x][k]则不是从结点x延伸出来的。找出是延伸结点x后，就知道需要再加a[1][i]-d[x][1]-1个非叶结点并且可得出每个新添加的每个非叶结点k到前i个叶结点的距离d[k][1]、d[k][2]、…、d[k][i]，但还需要计算出每个旧非叶结点k到叶结点i的距离d[k][i]，高效的计算方法： $d[k][i]=d[x][i]+max\{d[k][p]-d[x][p]\;\mathbf{|}\;1≤p<i\}$ ，枚举前i-1个叶结点即可得到。

AC 代码

#include <iostream>
#include <algorithm>
using namespace std;#define M 701
#define N 50
int a[N][N], d[M][N], c[M], m, n;bool check(int i, int j) {for (int k=1; k<i; ++k) if (a[i][k]-a[i][k-1] != d[j][k]-d[j][k-1]) return false;return true;
}void solve() {for (int i=m=0; i<n; ++i) for (int j=0; j<n; ++j) cin >> a[i][j];for (int j=a[0][1]-1; j>0; --j) d[m][0] = m+1, d[m][1] = j, c[m++] = 2;for (int i=2; i<n; ++i) for (int j=0; j<m; ++j) if (check(i, j)) {++c[j]; d[j][i] = a[i][0]-d[j][0];for (int k=0, dd; k<m; ++k) {for (int p=dd=0; p<i; ++p) dd = max(dd, d[k][p]-d[j][p]);d[k][i] = d[j][i]+dd;}for (int k=1; k<d[j][i]; ++k) {for (int p=0; p<i; ++p) d[m][p] = d[j][p]+k;d[m][i] = d[j][i]-k; c[m++] = 2;}break;}sort(c, c+m); cout << c[0];for (int i=1; i<m; ++i) cout << ' ' << c[i];cout << endl;
}int main() {while (cin>>n && n) solve();return 0;
}