hihocoder 1490 Tree Restoration

构造。

从最后一层开始往上构造。最后一层肯定都是叶子结点,距离为2的肯定是同一个父亲,确定好了父亲之后,可以确定上一层每个节点之间的距离,以及上一层每个节点到还未确定的叶子节点之间的距离。

#include<bits/stdc++.h>
using namespace std; int n,m,k;
vector<int>v[];
int A[],L[],h[];
int D[][];
int f[]; int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++) scanf("%d",&A[i]);
for(int i=;i<=m;i++)
{
while(A[i]--)
{
int x; scanf("%d",&x);
v[i].push_back(x);
}
}
for(int i=;i<=k;i++) scanf("%d",&L[i]),h[L[i]]=;
for(int i=;i<=k;i++) for(int j=;j<=k;j++) scanf("%d",&D[L[i]][L[j]]); for(int i=m;i>=;i--)
{
int last = ;
int now = ;
while()
{
if(now==v[i].size()) break; while()
{
if(h[v[i-][last]]==) last++;
else break;
} f[v[i][now]] = v[i-][last]; now++;
while()
{
if(now==v[i].size()) break;
if(D[v[i][now]][v[i][now-]]!=) {last++; break;}
f[v[i][now]] = v[i-][last]; now++;
}
} for(int j=;j<v[i].size();j++)
for(int t=;t<v[i].size();t++)
D[f[v[i][j]]][f[v[i][t]]]=D[v[i][j]][v[i][t]]-; for(int j=;j<v[i].size();j++)
for(int t=;t<=k;t++)
D[f[v[i][j]]][L[t]]=D[L[t]][f[v[i][j]]]=D[v[i][j]][L[t]]-;
} for(int i=;i<=n;i++)
{
printf("%d",f[i]);
if(i<n) printf(" ");
else printf("\n");
} return ;
}
上一篇:Tree Restoration Gym - 101755F (并查集)


下一篇:201521123111《Java程序设计》第8周学习总结